Volume 2 (2006) Article 2 pp. 19-51

Proving Integrality Gaps without Knowing the Linear Program

by Sanjeev Arora, Béla Bollobás, László Lovász, and Iannis Tourlakis

Received: June 1, 2005
Published: February 3, 2006
DOI: 10.4086/toc.2006.v002a002

Download article from ToC site:
[PS (771K)]    [PS.GZ (192K)]    [PS.ZIP (192K)]
[PDF (336K)]    [DVI (281K)]    [ZIP (85K)]
Misc.:
[HTML Bibliography] [Bibliography Source] [BibTeX] 
[About the Author(s)]
Keywords: linear programming, inapproximability, approximation algorithms, NP-hard problems, integrality gaps, lift-and-project, vertex cover
Categories:
ACM Classification: G.1.6, F.1.3
AMS Classification: 68Q17, 90C05, 90C57

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.