Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
The vertex cover problem is one of the most important and intensively studied combinatorial optimization problems. Khot and Regevproved that the problem is NP-hard to approximate within a factor2 - ∈, 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 in approximability result for the problem is due to Dinur and Safra: 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 vertex cover within a factor of 2-∈ has super-polynomially many inequalities. As a direct consequence of our methods, we also establish that LP relaxations (as well as SDP relaxations) that approximate the independent set problem within any constant factor have super-polynomially many inequalities. © 2015 IEEE.
Volkan Cevher, Grigorios Chrysos, Efstratios Panteleimon Skoulakis
Maryna Viazovska, Matthew De Courcy-Ireland, Maria Margarethe Dostert