Tight integrality gaps for Lovasz-Schrijver LP relaxations of vertex cover and max cut

We study linear programming relaxations of Vertex Cover and Max Cutarising 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 thatthe integrality gap remains at least 2-ε after Ω ε (log n) rounds, where n is the number ofvertices, and Tourlakis proves that integrality gap remains at least 1.5-ε after Ω((log n) 2 ) rounds. Fernandez de laVega and Kenyon prove that the integrality gap of Max Cut is at most 12 + ε after any constant number of rounds. (Theirresult also applies to the more powerful Sherali-Adams method. We prove that the integrality gap of Vertex Cover remains at least 2-ε after Ω ε (n) rounds, and that theintegrality gap of Max Cut remains at most 1/2 +ε after Ω ε (n) rounds.

Authors

• Grant Schoenebeck
• Luca Trevisan 0001
• Madhur Tulsiani

Keywords

• Lovasz-Schrijver hierarchy
• approximation algorithms
• integrality gap
• linear programming