CMU-CS-17-115Computer Science Department School of Computer Science, Carnegie Mellon University
CMU-CS-17-115
Euiwoong Lee May 2017 Ph.D. Thesis
Keywords:
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.
449 pages
Frank Pfenning, Head, Computer Science Department
| |

Return to:
SCS Technical Report Collection This page maintained by reports@cs.cmu.edu |