Approximation of Partial Capacitated Vertex Cover.

Reuven Bar-Yehuda Guy Flysher Julián Mestre Dror Rawitz

Published in: ESA (2007)

Keyphrases

constant factor
approximation algorithms
vertex cover
np hard
approximation ratio

special case
minimum cost
polynomial time approximation
worst case
precedence constraints

optimal solution
approximation guarantees
scheduling problem
integer programming
routing problem

branch and bound algorithm
lot sizing
undirected graph
linear program
computational complexity