ECCC-Report TR06-098https://eccc.weizmann.ac.il/report/2006/098Comments and Revisions published for TR06-098en-usThu, 17 Aug 2006 04:32:49 +0300
Paper TR06-098
| A Linear Round Lower Bound for Lovasz-Schrijver SDP Relaxations of Vertex Cover |
Grant Schoenebeck,
Luca Trevisan,
Madhur Tulsiani
https://eccc.weizmann.ac.il/report/2006/098We 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$.
Thu, 17 Aug 2006 04:32:49 +0300https://eccc.weizmann.ac.il/report/2006/098