Theory of Computing Article Abstract
------------------------------------
Title     : Proving Integrality Gaps without Knowing the Linear Program
Authors   : Sanjeev Arora, B{\'e}la Bollob{\'a}s, L{\'a}szl{\'o} Lov{\'a}sz, Iannis Tourlakis
Volume    : 2
Number    : 2
Pages     : 19-51
URL       : http://www.theoryofcomputing.org/articles/main/v002/a002/index.html

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.