Approximation Algorithms for Certain Network Improvement Problems.
Sven Oliver KrumkeMadhav V. MaratheHartmut NoltemeierR. RaviS. S. RaviPublished in: J. Comb. Optim. (1998)
Keyphrases
- approximation algorithms
- vertex cover
- network design problem
- np hard
- np hardness
- approximation schemes
- worst case
- randomized algorithms
- special case
- facility location problem
- exact algorithms
- np complete
- minimum cost
- quadratic program
- set cover
- approximation ratio
- network flow
- learning algorithm
- primal dual
- complex networks
- network structure
- search algorithm