[Metric 2011] Konstantinos Georgiou

-------
METRIC 2011 Trimester at Institut Henri Poincaré (Paris, France, Jan-Mar 2011)
-------
Workshop on Metric embeddings, algorithms  and hardness of approximation
January 17-21, 2011
-------
Jan 20, 13:30-14:30
Konstantinos Georgiou (U. 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 that P is not equal to NP, only gives 1.36 inapproximability. Closing this gap is one of the most challenging open problems in the theory of approximation algorithms. In this presentation we discuss 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 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. Both families of SDPs have given best algorithms known for a number of combinatorial problems. At the same time, showing negative results for SDPs for combinatorial problems with hard constraints (e.g. for Vertex Cover) has been a challenging task. For families of SDPs as above, we use geometric arguments to show why they fail to approximate Vertex Cover within factor strictly better than 2.