Published: February 3, 2006
Abstract: [Plain Text Version]
Proving integrality gaps for linear relaxations of NP optimization problems is a difficult task and usually undertaken on a case-by-case basis. We initiate a more systematic approach. We prove an integrality gap of $2 -o(1)$ for three families of linear relaxations for VERTEX COVER, and our methods seem relevant to other problems as well.