A better approximation ratio for the Vertex Cover problem

George Karakostas

Published in: Electron. Colloquium Comput. Complex. (2004)

Keyphrases

vertex cover
approximation ratio
approximation algorithms
np hard
special case
worst case
minimum cost
precedence constraints
polynomial time approximation
lower bound
optimal solution
search algorithm
computational complexity
branch and bound algorithm
constant factor