Antoulas, A. C.; Zhu, B.; Zhang, Q.; York, B.; O'Malley, B. W.; Dacso, C. C.: A novel mathematical method for disclosing oscillations in gene transcription: A comparative study. PLoS ONE 13 (9), e0198503 (2018)
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.