Dependent rounding and its applications to approximation algorithms.

Rajiv Gandhi Samir Khuller Srinivasan Parthasarathy Aravind Srinivasan

Published in: J. ACM (2006)

Keyphrases

approximation algorithms
np hard
special case
worst case
facility location problem
set cover
network design problem
vertex cover
open shop
minimum cost
approximation schemes
exact algorithms
primal dual
approximation ratio
undirected graph
constant factor
randomized algorithms
optimization problems
genetic algorithm