Arora, Sanjeev; Bollobás, Béla; Lovász, László; Tourlakis, Iannis Proving integrality gaps without knowing the linear program. (English) Zbl 1213.68306 Theory Comput. 2, Paper No. 2, 19-51 (2006). Summary: 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. Cited in 24 Documents MSC: 68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) 90C05 Linear programming 90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut Keywords:linear programming; inapproximability; approximation algorithms; NP-hard problems; integrality gaps; lift-and-project; vertex cover PDFBibTeX XMLCite \textit{S. Arora} et al., Theory Comput. 2, Paper No. 2, 19--51 (2006; Zbl 1213.68306) Full Text: DOI