2026-09-23T06:35:19Z https://www.ideals.illinois.edu/oai-pmh

oai:www.ideals.illinois.edu:2142/121437 2023-12-13 col_2142_5131 col_2142_10761 com_2142_5130 com_2142_10755 com_2142_234

Chekuri, Chandra Chekuri, Chandra Har-Peled, Sariel Chandrasekaran, Karthekeyan Mishra, Nina 2023-08 application/pdf en text Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2023-12-04 without embargo terms The student, Manuel Torres, accepted the attached license on 2023-06-28 at 11:20. The student, Manuel Torres, submitted this Dissertation for approval on 2023-06-28 at 16:11. This Dissertation was approved for publication on 2023-06-29 at 14:38. DSpace SAF Submission Ingestion Package generated from Vireo submission #19472 on 2023-12-04 at 17:00:16 Combining combinatorial and LP-based methods for better and faster approximation algorithms Torres, Manuel R 2023-06-29 Theoretical Computer Science Algorithms Approximation Algorithms Combinatorial Optimization Linear Programming Dense Subgraph Discovery We study several combinatorial optimization problems and develop approximation algorithms to solve them. Considering the rapid growth of data set sizes, our focus is the design of fast approximation algorithms. Many of the approximation algorithms we develop are based on linear programming (LP) relaxations. We design fast algorithms for both solving and rounding LPs. Our fast LP solvers build upon recent improvements used to solve LPs efficiently, such as those based on the multiplicative weight updates framework. The first problem we consider is the problem of packing integer programs (PIPs), which are problems of the form $\max\{\langle c, x \rangle : x \in \{0,1\}^n, Ax \le b\}$ where A, b, and c are all nonnegative. Let $W = \max_{i,j : A_{i,j} > 0} \frac{b_i}{A_{i,j}}$ be the width of the given PIP. We present randomized algorithms, obtaining approximations in terms of the maximum column sum $\Delta_1$ of A when W > 1, and we show that it is NP-hard to approximate PIPs solely in terms of $\Delta_1$ when W = 1. The second problem we consider is the bounded degree minimum spanning tree problem (BD-MST), an NP-hard variant of the minimum spanning tree problem where we also want to satisfy degree constraints. We design a near-linear time approximation algorithm for BD-MST by speeding up algorithms for solving the natural LP relaxation and for a known dependent randomized rounding technique called swap rounding. We extend these results to a generalization known as the crossing spanning tree problem. The third problem we consider is the densest subgraph problem (DSG). We make three main contributions. The first is a fast $(1-\epsilon)$-approximation based on maximum flow. The second result resolves a conjecture from previous work showing that an iterative greedy peeling algorithm Greedy++ in fact converges to a near-optimal solution. For the third contribution, using the lens of supermodularity, we unify and generalize many existing notions of density in the literature, referring to this problem as the densest supermodular subset problem (DSS). This supermodular perspective facilitated the convergence proof of Greedy++. We give a simple peeling algorithm for DSS and prove the convergence of an iterative generalization similar to Greedy++. Finally, we consider the p-mean densest subgraph problem (p-mean DSG) where p is a parameter defining the objective, which generalizes both DSG and the maximum k-core. For $p \ge 1$, the objective is supermodular and thus a special case of DSS. We show how to speed up the running time of the simple peeling algorithm for p-mean DSG. For p < 1, we show that the problem is NP-hard and develop approximation algorithms. We supplement our theoretical results with empirical evaluation of our algorithms on real-world graphs. Text eng https://hdl.handle.net/2142/121437 Copyright 2023 Manuel Torres Ph.D. Dissertation Computer Science University of Illinois at Urbana-Champaign Computer Science