How to Pay, Come What May: Approximation Algorithms for Demand-Robust Covering Problems.

Kedar Dhamdhere Vineet Goyal R. Ravi Mohit Singh

Published in: FOCS (2005)

Keyphrases

approximation algorithms
vertex cover
np hard
np hardness
approximation schemes
randomized algorithms
special case
network design problem
minimum cost
search algorithm
worst case
optimization problems
exact algorithms
precedence constraints
quadratic program