A Linear Round Lower Bound for Lovasz-Schrijver SDP Relaxations of Vertex Cover

Grant Schoenebeck, Luca Trevisan, and Madhur Tulsiani


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 for a stronger relaxation that is, however, incomparable with two rounds of LS+ and is strictly weaker than the relaxation resulting from a constant number of rounds.

We prove that the integrality gap remains at least 7/6-ε after cε n rounds, where n is the number of vertices and cε > 0 is a constant that depends only on ε.


 [ back to Grant's homepage]