Computer Science Department
School of Computer Science, Carnegie Mellon University
Optimal Approximabilities beyond CSPs
Approximation algorithms, Hardness of approximation, Combinatorial optimization, Constraint satisfaction problems, Coloring problems, Covering problems, Cut problems, Convex relaxations, LP/SDP hierarchies, Unique games conjecture
The theory of approximation algorithms has seen great progress since
the nineties, and the optimal approximation ratio was discovered for many
fundamental combinatorial optimization problems. This progress has been
most successfully applied to a subclass of optimization problems called maximum
constraint satisfaction problems ( MAX CSPs), where there is a simple semidefinite programming based algorithm provably optimal for every problem in this class under the Unique Games Conjecture. Such a complete understanding is not known for other basic classes such as coloring, covering, and graph cut problems.
This thesis tries to expand the frontiers of approximation algorithms, with
respect to the range of optimization problems as well as mathematical tools for
algorithms and hardness. We show tight approximabilities for various fundamental
problems in combinatorial optimization beyond MAX CSP. It consists of the following five parts:
- CSPs: We introduce three variants of MAX CSP, called HARD CSP,
BALANCE CSP, and SYMMETRIC CSP. Our results show that current
hardness theories for MAX CSP can be extended to its generalizations
(HARD CSP, BALANCE CSP) to prove much stronger hardness, or can
be significantly simplified for a special case (SYMMETRIC CSP).
- Applied CSPs: Numerous new optimization problems have emerged
since the last decade, as computer science has more actively interacted
with other fields. We study three problems called UNIQUE COVERAGE,
GRAPH PRICING, and decoding LDPC codes, motivated by networks,
economics, and error-correcting codes. Extending the tools for MAX CSP,
we show nearly optimal hardness results or integrality gas for these problems.
- Coloring: We study the complexity of hypergraph coloring problems when
instances are promised to have a structure much stronger than admitting
a proper 2-coloring, and prove both algorithmic and hardness results.
For both algorithms and hardness, we give unifed frameworks that can
be used for various settings.
- H-TRANSVERSAL: We study the problem H-TRANSVERSAL, where given a graph G and a fixed "pattern" graph H, the goal is to remove the minimum
number of vertices from G to make sure it does not include H as a subgraph. We show an almost complete characterization of the approximability
of H-TRANSVERSAL depending on properties of H. One of our algorithms reveals a new connection between path transversal and graph partitioning.
- We also study various cut problems on graphs, where the goal is to remove
the minimum number of vertices or edges to cut desired paths or
cycles. We present a general tool called length-control dictatorship tests to prove strong hardness results under the Unique Games Conjecture,
which allow us to prove improved hardness results for multicut, bicut,
double cut, interdiction, and firefigher problems.
Venkatesan Guruswami (Chair)
R. Ravi (Tepper/CSD)
Ola Svensson (École Polytechnique Fédérale de Lausanne (EPFL))
Frank Pfenning, Head, Computer Science Department
Andrew W. Moore, Dean, School of Computer Science