No Small Linear Program Approximates Vertex Cover within a Factor 2 - e.
Abbas BazziSamuel FioriniSebastian PokuttaOla SvenssonPublished in: FOCS (2015)
Keyphrases
- linear program
- vertex cover
- linear programming
- approximation algorithms
- semi infinite
- np hard
- column generation
- optimal solution
- primal dual
- integer program
- dynamic programming
- mixed integer
- objective function
- partial order
- integer programming
- convex functions
- long run
- mixed integer programming
- computational complexity