Vortragender: Prof. Dr. Samuel Fiorini Gastgeber: veranstaltet von den Fakultäten für Elektrotechnik, für Mathematik und dem Forschungszentrum Dynamische Systeme der OVGU sowie dem MPI Magdeburg
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. [mehr]
Zur Redakteursansicht