CMU-CS-14-125Computer Science Department School of Computer Science, Carnegie Mellon University
CMU-CS-14-125
Yuan Zhou August 2014 Ph.D. Thesis
Keywords:
Approximation Algorithms, Hardness of Approximation, Combinatorial
Optimization, Convex Relaxation Hierarchies, Linear Programming, Semidefinite
Programming
Combinatorial optimization encompasses a wide range of important com-
putational tasks such as UNIFORMSPARSESTCUT
(also known as NORMALIZEDCUT), MAXCUT, TRAVELINGSALESMANPROBLEM, and VERTEXCOVER.
Most combinatorial optimization problems are In the last two decades, the research frontier of approximation algorithm design has been greatly advanced thanks to the convex optimization techniques such as linear and semidefinite programming. However, the exact approximability for many problems remains mysterious but some common barriers for progress revolving around a problem called Unique Games has been identified. The limitations of convex relaxation techniques answer the question that what is the best possible approximation guarantee to be achieved by the state-of-the-art algorithmic design tools, and shed light on the real approximability. Therefore, the study of the power of convex relaxations becomes a valuable new research direction to get around the current barrier on hardness proofs.
In this thesis, using constraint satisfaction problems, assignment problems,
graph partitioning problems (BALANCEDSEPARATOR, UNIFORMSPARSESTCUT, DENSE This thesis also contains a collection of approximation algorithms for almost satisfiable constraint satisfaction problems and MAXBISECTION, detection of almost isomorphic trees, and estimation of the 2 → 4 operator norm of random linear operators. There are also a few (conditional) hardness of approximation results for almost satisfiable linear systems over integers, almost satisfiable MAXHORN3-SAT, and detection of almost isomorphic graphs. 345 pages
Frank Pfenning, Head, Computer Science Department
| |

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