No Small Linear Program Approximates Vertex Cover within a Factor 2-ε.

Abbas Bazzi Samuel Fiorini Sebastian Pokutta Ola Svensson

Published in: CoRR (2015)

Keyphrases

linear program
vertex cover
linear programming
approximation algorithms
semi infinite
optimal solution
np hard
column generation
partial order
primal dual
integer program
dynamic programming
objective function
mixed integer
planar graphs
special case
convex functions
probabilistic model
lower bound