Towards Optimal Integrality Gaps for Hypergraph Vertex Cover in the Lovász-Schrijver Hierarchy.

Iannis Tourlakis

Published in: APPROX-RANDOM (2005)

Keyphrases

vertex cover
approximation algorithms
optimality criterion
optimal solution
dynamic programming
objective function
worst case
finding optimal
linear programming
planar graphs