TR06-098 Authors: Grant Schoenebeck, Luca Trevisan, Madhur Tulsiani

Publication: 17th August 2006 04:32

Downloads: 972

Keywords:

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$.