Proving Integrality Gaps without Knowing the Linear Program

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.

Authors

• Sanjeev Arora
• Béla Bollobás
• László Lovász 0001

Keywords

• Approximation algorithms
• Polynomials
• NP-hard problem
• Upper bound
• Cost function
• Educational institutions
• Ellipsoids
• Linear programming
• Computer science
• Computational modeling
• Integrality Gap
• Vertex Cover
• Linear Relaxation
• Independent Set
• Estimation Algorithm
• Optimum Solution
• Minimum Coverage
• Auxiliary Variables
• Pair Distance
• Random Graph
• Linear Graph
• Decades Of Work
• Polytope
• Maximum Independent Set
• Induced Subgraph
• Number Of Graphs
• Integer Vector
• Sparse Conditions