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       : https://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.