A Better Approximation Ratio for the Vertex Cover Problem.

George Karakostas

Published in: ICALP (2005)

Keyphrases

vertex cover
approximation ratio
approximation algorithms
np hard
special case
worst case
minimum cost
constant factor
approximation guarantees
greedy algorithm
polynomial time approximation
precedence constraints
undirected graph
reinforcement learning
search algorithm
scheduling problem