Approximation Algorithms for Partial Covering Problems.

Rajiv Gandhi Samir Khuller Aravind Srinivasan

Published in: ICALP (2001)

Keyphrases

approximation algorithms
vertex cover
approximation schemes
np hard
worst case
randomized algorithms
np hardness
special case
facility location problem
np complete
primal dual
network design problem
set cover
optimization problems
minimum cost
exact algorithms
constant factor