Samuel Fiorini
No Small Linear Program Approximates Vertex Cover within a Factor 2-ε
Prof. Dr. Samuel Fiorini
Université Libre de Bruxelles
Time & Place
The presentation on December 8, 2015 will be given at the Lukasklause, Schleinufer 1, Magdeburg and starts at 5.00 p.m.
Abstract
The vertex cover problem is one of the most important and intensively studied combinatorial optimization problems. Khot and Regev (2003) proved that the problem is NP-hard to approximate within a factor 2-ε, assuming Khot's famous Unique Games Conjecture (UGC). This is tight because the problem has an easy 2-approximation algorithm.
We prove the following unconditional result about linear programming (LP) relaxations of the problem: every LP relaxation that approximates vertex cover within a factor 2-ε has super-polynomially many inequalities.