On Hierarchies of Strong SDP Relaxations for Combinatorial Optimization Problems

Studying the approximation threshold of NP-hard optimization problems, i.e. the ratio of the objective value achievable by a polynomial time algorithm to that of the optimal solution is an important field in theoretical computer science. In the past two decades there has been significant development both in terms of finding good approximation algorithms, e.g. through the use of semidefinite programming and hardness of approximation, e.g. the development of Probabilistically Checkable Proofs and Unique Games Conjecture. Trying to prove lower bounds for the approximation threshold of an optimization problem, one could take one of two approaches. In the first approach, one proves such lower bounds under a complexity assumption like P =/= NP or Unique Games Conjecture. In the second approach, one studies the behaviour of prominent algorithmic schemes, such as Linear Programming (LP) and Semidefinite Programming (SDP) relaxations for the problem of interest. There, the measure of efficiency is the integrality gap which sets the approximation limitation of the algorithms based on these relaxations. In this work we study the integrality gap of families of strong LP and SDP relaxations for a number of combinatorial optimization problems. The relaxations come from the context of Lift-and-Project systems. There one starts from a standard (weak) relaxation from a problem and iteratively adds more constraints to make the relaxation stronger, i.e. closer to an exact formulation of the problem. We mostly study the performance of the Sherali-Adams SDP relaxations. Specifically, the main contributions of this thesis are as follows. • We show optimal integrality gaps for the level-\Theta(n) Sherali-Adams SDP relaxation of MAX k-CSP_q(P) for any predicate P:[q]^k -> {0,1} satisfying a technical condition, which we call being promising. Our result show that for such predicates MAX k-CSP_q (P) cannot be approximated (beyond a trivial approximation) by the Sherali-Adams SDP relaxations of even very high level. Austrin and Håstad (SIAM J. Comput., 2011) show that a random predicate is almost surely promising. • We complement the above result by showing that for some class of predicates which are not promising MAX k-CSP_q(P) can be approximated (beyond the trivial approximation) by its canonical SDP relaxation. • We show optimal integrality gap lower bounds for level-poly(n) Sherali-Adams SDP relaxations of Quadratic Programming. We also present superconstant integrality gap lower bounds for superconstant levels of the same hierarchy for MaxCutGain. • We show optimal integrality gap lower bounds for the level-5 Sherali-Adams SDP relaxation of Vertex Cover. We also conjecture a positivity condition on the Taylor expansion of a certain function which, if proved, shows optimal integrality gaps for any constant level of the Sherali-Adams SDP hierarchy for Vertex Cover. • We revisit the connection between integrality gap lower bounds and the Frankl-Rödl theorem (Trans. of the AMS, 1987). We prove a new density version of that theorem which can be interpreted as a new isoperimetric inequality of the Hamming cube. Using this inequality we prove integrality gap lower bounds for the Lovász-Schrijver SDP (resp. Sherali-Adams LP) relaxation of Vertex Cover (resp. Independent Set) in degree bounded graphs.Ph