Friday, April 23, 2010
3:30 pm, MC 5158

Konstantinos Georgiou
University of Toronto

Fooling Strong LP and SDP Relaxations for Vertex Cover

A vertex cover of a graph is a subset of the vertices touching all the edges. Finding the minimum Vertex Cover is one of the classical NP-hard problems whose inapproximability is yet unresolved; while a 2-approximation algorithm is easy to design, the best lower bound known, modulo a standard complexity assumption, only gives 1.36 inapproximability. Closing this gap is one of the most challenging open problems in the theory of approximation algorithms. In our work we study the inapproximability of Vertex Cover for restricted, yet powerful models of computation based on Linear Programming (LP) and Semidefinite Programming (SDP) relaxations. Our results are negative and give strong evidence that the true approximability of Vertex Cover is 2.
In 1995, Goemans and Kleinberg showed that the standard SDP relaxation for Vertex Cover has an integrality gap of 2. Since then, a lot of effort has been devoted in showing that the integrality gap remains 2 even after tightening this relaxation. Our line of study deals with hierarchies of SDPs derived by strong systematic procedures. These are, first, SDPs tightened by hypermetric inequalities, and second, SDPs derived by the Sherali-Adams SDP system. The first system has given the best algorithms known for a series of combinatorial optimization problems. The second is known to exhibit an optimal behavior for a special class of constraint satisfaction problems under a strong complexity assumption.