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

Grant Schoenebeck, Luca Trevisan, and Madhur Tulsiani


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-ε after Ωε(log n) rounds, where n is the number of vertices, and Tourlakis proves that integrality gap remains at least 1.5-ε after Ωε((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-ε after Ωε(n) rounds, and that the integrality gap of Max Cut remains at most 1/2 + ε after Ωε(n) rounds. The result for Max Cut shows a gap between the approximation provided by linear versus semidefinite programmming relaxations.


Versions