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

Grant Schoenebeck, Luca Trevisan, Madhur Tulsiani

Browse the full STOC paper archive.