Volume 2 (2006)
Article 2 pp. 19-51
Proving Integrality Gaps without Knowing the Linear Program
Received: June 1, 2005
Published: February 3, 2006
Published: February 3, 2006
Keywords: linear programming, inapproximability, approximation algorithms, NP-hard problems, integrality gaps, lift-and-project, vertex cover
Categories: algorithms, approximation algorithms, integrality gap, combinatorial optimization, lower bounds
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.
Licensed under a Creative Commons License