Approximation algorithms for semi-random partitioning problems.

Konstantin Makarychev Yury Makarychev Aravindan Vijayaraghavan

Published in: STOC (2012)

Keyphrases

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