A better approximation ratio for the vertex cover problem.

George Karakostas

Published in: ACM Trans. Algorithms (2009)

Keyphrases

vertex cover
approximation ratio
approximation algorithms
np hard
special case
worst case
minimum cost
precedence constraints
polynomial time approximation
approximation guarantees
constant factor
knapsack problem
undirected graph
computational complexity
linear programming
parameter estimation