Combining combinatorial and LP-based methods for better and faster approximation algorithms

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\}ⁿ, Ax \le b\} where A, b, and c are all nonnegative. Let W = \max_{i,j : Ai,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₁ of A when W > 1, and we show that it is NP-hard to approximate PIPs solely in terms of \Delta₁ 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-ε)-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.

Name thesis:degree_name

Ph.D.

Level thesis:degree_level

Dissertation

Discipline thesis:degree_discipline

Computer Science

Grantor

University of Illinois at Urbana-Champaign

Year dc:date

2023

Author dc:creator

• Torres, Manuel R

Contributors dc:contributor

• Chekuri, Chandra
• Har-Peled, Sariel
• Chandrasekaran, Karthekeyan
• Mishra, Nina

• Theoretical Computer Science
• Algorithms
• Approximation Algorithms
• Combinatorial Optimization
• Linear Programming
• Dense Subgraph Discovery

Statement dc:rights

• Copyright 2023 Manuel Torres

Language dc:language

en, eng

Handle dc:identifier

https://hdl.handle.net/2142/121437

OAI record oai:identifier

https://www.ideals.illinois.edu/oai-pmh?verb=GetRecord&metadataPrefix=etdms&identifier=oai%3Awww.ideals.illinois.edu%3A2142%2F121437