Rätze, K.; Jokiel, M.; Kaiser , N. M.; Sundmacher, K.: Cyclic Operation of a Semi-Batch Reactor for the Hydroformylation of Long-Chain Olefins and Integration in a Continuous Production Process. Chemical Engineering Journal (angenommen)
Hädicke, O.; Kamp von, A.; Aydogan, T.; Klamt, S.: OptMDFpathway: Identification of metabolic pathways with maximal thermodynamic driving force and its application for analyzing the endogenous CO2 fixation potential of Escherichia coli. PLoS Computational Biology 14 (9), e1006492 (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.