Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR06-098 | 17th August 2006 00:00

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


Authors: Grant Schoenebeck, Luca Trevisan, Madhur Tulsiani
Publication: 17th August 2006 04:32
Downloads: 1462


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

ISSN 1433-8092 | Imprint