Approximation algorithms for the 0-extension problem.
Gruia CalinescuHoward J. KarloffYuval RabaniPublished in: SODA (2001)
Keyphrases
- approximation algorithms
- special case
- np hard
- worst case
- vertex cover
- facility location problem
- approximation ratio
- minimum cost
- network design problem
- constant factor
- randomized algorithms
- np hardness
- set cover
- approximation schemes
- combinatorial auctions
- polynomial time approximation
- disjoint paths
- constant factor approximation
- objective function
- precedence constraints
- exact algorithms
- approximation guarantees
- metaheuristic
- linear programming
- open shop