Revision #1 Authors: Grant Schoenebeck, Luca Trevisan, Madhur Tulsiani

Accepted on: 18th October 2006 00:00

Downloads: 961

Keywords:

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.

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

Publication: 17th October 2006 01:32

Downloads: 1034

Keywords:

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.