Parallel approximation algorithms for facility-location problems.
Guy E. BlellochKanat TangwongsanPublished in: SPAA (2010)
Keyphrases
- approximation algorithms
- facility location problem
- np hard
- special case
- vertex cover
- worst case
- approximation ratio
- minimum cost
- set cover
- randomized algorithms
- network design problem
- primal dual
- precedence constraints
- constant factor approximation
- shared memory
- polynomial time approximation
- lower bound
- demand points
- open shop
- integer programming
- branch and bound algorithm
- constraint satisfaction
- optimal solution