REPORTS > DETAIL:
Paper:
TR06-152 | 6th December 2006 00:00
Tight integrality gaps for Vertex Cover SDPs in the Lovasz-Schrijver hierarchy
TR06-152 Authors: Konstantinos Georgiou, Avner Magen, Iannis Tourlakis
Publication: 15th December 2006 07:53
Downloads: 137
Keywords:
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).