Improved Approximation Algorithms for the Partial Vertex Cover Problem.

Eran Halperin Aravind Srinivasan

Published in: APPROX (2002)

Keyphrases

vertex cover
approximation algorithms
special case
np hard
worst case
minimum cost
partial order
constant factor
undirected graph
primal dual
precedence constraints
scheduling problem
knapsack problem
approximation ratio
planar graphs