Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > LOVASZ-SCHRIJVER HIERARCHY:
Reports tagged with Lovasz-Schrijver hierarchy:
TR06-132 | 17th October 2006
Grant Schoenebeck, Luca Trevisan, Madhur Tulsiani

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

Revisions: 1

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

ISSN 1433-8092 | Imprint