No Small Linear Program Approximates Vertex Cover Within a Factor 2 − ɛ

Abbas Bazzi (), Samuel Fiorini (), Sebastian Pokutta () and Ola Svensson ()
Additional contact information
Abbas Bazzi: School of Computer and Communication Sciences, École Polytechnique Fédérale de Lausanne, Lausanne, France CH-1015
Samuel Fiorini: Département de Mathématique, Université Libre de Bruxelles, Brussels, Belgium B-1050
Sebastian Pokutta: H. Milton Stewart School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, Georgia 30318
Ola Svensson: School of Computer and Communication Sciences, École Polytechnique Fédérale de Lausanne, Lausanne, France CH-1015

Mathematics of Operations Research, 2019, vol. 44, issue 1, 147-172

Abstract: The vertex cover problem is one of the most important and intensively studied combinatorial optimization problems. Khot and Regev [Khot S, Regev O (2008) Vertex cover might be hard to approximate to within 2 − ɛ . J. Comput. System Sci. 74(3):335–349] proved that the problem is NP-hard to approximate within a factor 2 − ɛ , assuming the unique games conjecture (UGC). This is tight because the problem has an easy 2-approximation algorithm. Without resorting to the UGC, the best inapproximability result for the problem is due to Dinur and Safra [Dinur I, Safra S (2005) On the hardness of approximating minimum vertex cover. Ann. Math. 162(1):439–485]: vertex cover is NP-hard to approximate within a factor 1.3606. We prove the following unconditional result about linear programming (LP) relaxations of the problem: every LP relaxation that approximates the vertex cover within a factor 2 − ɛ has super-polynomially many inequalities. As a direct consequence of our methods, we also establish that LP relaxations (as well as semidefinite programming relaxations) that approximate the independent set problem within any constant factor have a super-polynomial size.

Keywords: extended; formulations:; hardness; of; approximation:; independent; set:; linear; programming:; vertex; cover (search for similar items in EconPapers)
Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
https://doi.org/10.1287/moor.2017.0918 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormoor:v:44:y:2019:i:1:p:147-172

Access Statistics for this article

More articles in Mathematics of Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().