Tight integrality gaps for Lovasz-Schrijver LP relaxations of vertex cover and max cut
Grant Schoenebeck, Luca Trevisan, Madhur Tulsiani · 2007
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.