| Most combinatorial optimization problems are NP-hard to solve optimally. A natural approach to cope with this intractability is to design an "approximation algorithm"---an efficient algorithm that is guaranteed to produce a good approximation to the optimum solution. The last two decades has witnessed tremendous developments in the design of approximation algorithms mostly fueled by convex optimization techniques such as linear or semidefinite programming.;In this thesis, we present algorithmic and lower bound results that characterize the power and limitations of these techniques on large classes of combinatorial optimization problems. The thesis identifies a specific simple semidefinite program and demonstrates the following: (1) This semidefinite program yields the optimal approximation to every problem in one of the large classes such as constraint satisfaction problems (CSP), metric labeling problems and ordering constraint satisfaction problems under the Unique Games Conjecture ( UGC). To show this, we exhibit a general black-box reduction from hard instances to a linear/semidefinite program to corresponding hardness results based on the UGC. Not only does this confirm a widely suspected connection, it settles the approximability of classic optimization problems such as CSPs, MULTIWAY CUT and MAXIMUM ACYCLIC SUBGRAPH under UGC. (2) The thesis presents a generic algorithm for constraint satisfaction problems (CSP) based on this semidefinite program. Irrespective of the truth of UGC, this generic algorithm is guaranteed to obtain an approximation at least as good as all known algorithms for specific CSPs. (3) Independent of the truth of UGC, the approximation obtained by this semidefinite program cannot be improved by any convex relaxation that is obtained by including any valid constraints on at most O(2(log log N)¼) vectors. |
