ECCC-Report TR06-132https://eccc.weizmann.ac.il/report/2006/132Comments and Revisions published for TR06-132en-usWed, 18 Oct 2006 00:00:00 +0200
Revision 1
| Tight Integrality Gaps for Lovasz-Schrijver LP Relaxations of Vertex Cover and Max Cut |
Grant Schoenebeck,
Luca Trevisan,
Madhur Tulsiani
https://eccc.weizmann.ac.il/report/2006/132#revision1We 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.
Wed, 18 Oct 2006 00:00:00 +0200https://eccc.weizmann.ac.il/report/2006/132#revision1
Paper TR06-132
| Tight Integrality Gaps for Lovasz-Schrijver LP Relaxations of Vertex Cover and Max Cut |
Grant Schoenebeck,
Luca Trevisan,
Madhur Tulsiani
https://eccc.weizmann.ac.il/report/2006/132We 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.
Tue, 17 Oct 2006 01:32:36 +0200https://eccc.weizmann.ac.il/report/2006/132