#### Withdraw

Loading…

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

#### Torres, Manuel R

Loading…

## Permalink

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

## 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

##### Graduate Dissertations and Theses at Illinois PRIMARY

Graduate Theses and Dissertations at Illinois#### Manage Files

Loading…

#### Edit Collection Membership

Loading…

#### Edit Metadata

Loading…

#### Edit Properties

Loading…

#### Embargoes

Loading…