Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR06-152 | 6th December 2006 00:00

Tight integrality gaps for Vertex Cover SDPs in the Lovasz-Schrijver hierarchy

RSS-Feed

Abstract:

We prove that the integrality gap after tightening the standard LP relaxation for Vertex Cover with Omega(sqrt(log n/log log n)) rounds of the SDP LS+ system is 2-o(1).



ISSN 1433-8092 | Imprint