Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR06-132 | 18th October 2006 00:00

Tight Integrality Gaps for Lovasz-Schrijver LP Relaxations of Vertex Cover and Max Cut

RSS-Feed




Revision #1
Authors: Grant Schoenebeck, Luca Trevisan, Madhur Tulsiani
Accepted on: 18th October 2006 00:00
Downloads: 3559
Keywords: 


Abstract:

We study linear programming relaxations of Vertex Cover and Max Cut
arising from repeated applications of the ``lift-and-project''
method of Lovasz and Schrijver starting from the standard linear
programming relaxation.

For Vertex Cover, Arora, Bollobas, Lovasz and Tourlakis prove that
the integrality gap remains at least $2-\epsilon$ after
$\Omega_\epsilon(\log n)$ rounds, where $n$ is the number of
vertices, and Tourlakis proves that integrality gap remains at least
$1.5-\epsilon$ after $\Omega((\log n)^2)$ rounds. Fernandez de la
Vega and Kenyon prove that the integrality gap of Max Cut is at most
$1/2 + \epsilon$ after any constant number of rounds. (Their
result also applies to the more powerful Sherali-Adams method.)

We prove that the integrality gap of Vertex Cover remains at least
$2-\epsilon$ after $\Omega_\epsilon (n)$ rounds, and that the
integrality gap of Max Cut remains at most $1/2 +\epsilon$ after
$\Omega_\epsilon(n)$ rounds.


Paper:

TR06-132 | 17th October 2006 00:00

Tight Integrality Gaps for Lovasz-Schrijver LP Relaxations of Vertex Cover and Max Cut





TR06-132
Authors: Grant Schoenebeck, Luca Trevisan, Madhur Tulsiani
Publication: 17th October 2006 01:32
Downloads: 3941
Keywords: 


Abstract:

We study linear programming relaxations of Vertex Cover and Max Cut
arising from repeated applications of the ``lift-and-project''
method of Lovasz and Schrijver starting from the standard linear
programming relaxation.

For Vertex Cover, Arora, Bollobas, Lovasz and Tourlakis prove that
the integrality gap remains at least $2-\epsilon$ after
$\Omega_\epsilon(\log n)$ rounds, where $n$ is the number of
vertices, and Tourlakis proves that integrality gap remains at least
$1.5-\epsilon$ after $\Omega((\log n)^2)$ rounds. We are not aware
of previous work on Lovasz-Schrijver linear programming relaxations
for Max Cut.

We prove that the integrality gap of Vertex Cover remains at least
$2-\epsilon$ after $\Omega_\epsilon (n)$ rounds, and that the
integrality gap of Max Cut remains at most $1/2 +\epsilon$ after
$\Omega_\epsilon(n)$ rounds. The result for Max Cut shows a gap
between the approximation provided by linear versus semidefinite
programmming relaxations.



ISSN 1433-8092 | Imprint