The theory of approximation algorithms has seen great progress since 90's, and the optimal approximation ratio was revealed for many fundamental combinatorial optimization problems. Despite this success for individual problems, our understanding is not complete to have a unified understanding of each class of problems. One of the most notable exceptions is an important subclass of CSPs called MAX CSP, 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:

1. 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).

2. 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 tools for MAX CSP, we show nearly optimal hardness results or integrality gas for these problems.

3. Coloring: We study 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 promises.

4. H-TRANSVERSAL: We study 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.

5. 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.

449 pages

Thesis Committee:
Venkatesan Guruswami (Chair)
Anupam Gupta
R. Ravi (Tepper/CSD)
Ryan O'Donnell
Ola Svensson (École Polytechnique Fédérale de Lausanne (EPFL))

Frank Pfenning, Head, Computer Science Department
Andrew W. Moore, Dean, School of Computer Science

Return to: SCS Technical Report Collection
School of Computer Science

This page maintained by [email protected]