Under the auspices of the Computational Complexity Foundation (CCF)
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-\epsilon$ after
$c_\epsilon n$ rounds, where $n$ is the number of vertices and $c_\epsilon>0$
is a constant that depends only on $\epsilon$.