Theory of Computing
-------------------
Title : Proving Integrality Gaps without Knowing the Linear Program
Authors : Sanjeev Arora, Bela Bollobas, Laszlo Lovasz, and Iannis Tourlakis
Volume : 2
Number : 2
Pages : 19-51
URL : http://www.theoryofcomputing.org/articles/v002a002
Abstract
--------
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.