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

Torres, Manuel R

Permalink

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

Description

Title

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

Author(s)

Torres, Manuel R

Issue Date

2023-06-29

Director of Research (if dissertation) or Advisor (if thesis)

Chekuri, Chandra

Doctoral Committee Chair(s)

Chekuri, Chandra

Committee Member(s)

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

Department of Study

Computer Science

Discipline

Computer Science

Degree Granting Institution

University of Illinois at Urbana-Champaign

Degree Name

Ph.D.

Degree Level

Dissertation

Keyword(s)

• theoretical computer science
• algorithms
• approximation algorithms
• combinatorial optimization
• linear programming
• dense subgraph discovery

Abstract

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.

Graduation Semester

2023-08

Type of Resource

Thesis

Copyright and License Information

Copyright 2023 Manuel Torres

Owning Collections