A Linear Round Lower Bound for Lovasz-Schrijver SDP Relaxations of Vertex Cover
Grant Schoenebeck, Luca Trevisan, Madhur Tulsiani · Proceedings - IEEE Conference on Computational Complexity/Proceedings · 2007
We study semidefinite programming relaxations of Vertex Cover arising from repeated applications of the LS+ "lift-and-project" method of Lovasz and Schrijver starting from the standard linear programming relaxation. Goemans and Kleinberg prove that after one round of LS+ the integrality gap remains arbitrarily close to 2. Charikar proves an integrality gap of 2, later strengthened by Hatami, Magen, and Markakis, for stronger relaxations that are, however, incomparable with two rounds of LS+. Subsequent work by Georgiou, Magen, Pitassi, and Tourlakis shows that the integrality gap remains 2 -epsiv after Omega (radiclog n-log log n ) rounds [?]. We prove that the integrality gap remains at least 7/6 - epsiv after cepsivn rounds, where n is the number of vertices and cepsiv> 0 is a constant that depends only on epsiv.