Tight integrality gaps for Vertex Cover SDPs in the Lovasz-Schriver Hierarchy

Toni Pitassi
University of Toronto

Thursday, March 22, 3:00 pm, Wean Hall 4625

Abstract

A vertex cover in a graph G=(V,E) is a subset S of the vertices such that every edge intersects S in at least one endpoint. The minimum vertex cover problem asks for the size of the minimum vertex cover in G. Determining how well we can approximate vertex cover is one of the outstanding open problems in the complexity of approximation. The best known approximation is a factor of 2, whereas the best inapproximability result of Dinur and Safra shows that it is NP hard to solve the problem within a factor of 1.36.

To get a better picture of the approximability of vertex cover, in light of our inability to resolve the issue with PCP-based methods, Arora-et-al sugggested ruling out good approximations for vertex cover by large families of algorithms. One such important family is the class of relaxations for vertex cover in the Lovasz-Schriver hierarchies.

In this talk, we will survey what is currently known, and present a new result showing that the integrality gap for vertex cover is 2-o(1), even after $\sqrt (\logn / \loglogn)$ rounds of the the SDP LS+ system of Lovasz and Schriver.

This is joint work with Konstantinos Georgiou, Avner Magen, and Iannis Tourlakis.