Improved combinatorial algorithms for the facility location and k-median problems
Top Cited Papers
- 20 January 2003
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 02725428,p. 378-388
- https://doi.org/10.1109/sffcs.1999.814609
Abstract
We present improved combinatorial approximation algorithms for the uncapacitated facility location and k-median problems. Two central ideas in most of our results are cost scaling and greedy improvement. We present a simple greedy local search algorithm which achieves an approximation ratio of 2.414+/spl epsiv/ in O/spl tilde/(n/sup 2///spl epsiv/) time. This also yields a bicriteria approximation tradeoff of (1+/spl gamma/, 1+2//spl gamma/) for facility cost versus service cost which is better than previously known tradeoffs and close to the best possible. Combining greedy improvement and cost scaling with a recent primal dual algorithm for facility location due to K. Jain and V. Vazirani (1999), we get an approximation ratio of 1.853 in O/spl tilde/(n/sup 3/) time. This is already very close to the approximation guarantee of the best known algorithm which is LP-based. Further combined with the best known LP-based algorithm for facility location, we get a very slight improvement in the approximation factor for facility location, achieving 1.728. We present improved approximation algorithms for capacitated facility location and a variant. We also present a 4-approximation for the k-median problem, using similar ideas, building on the 6-approximation of Jain and Vazirani. The algorithm runs in O/spl tilde/(n/sup 3/) time.Keywords
This publication has 16 references indexed in Scilit:
- Primal-dual approximation algorithms for metric facility location and k-median problemsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2003
- Analysis of a Local Search Heuristic for Facility Location ProblemsJournal of Algorithms, 2000
- Improved Approximation Algorithms for Capacitated Facility Location ProblemsPublished by Springer Nature ,1999
- Greedy Strikes Back: Improved Facility Location AlgorithmsJournal of Algorithms, 1999
- Bicriteria Network Design ProblemsJournal of Algorithms, 1998
- Rounding via treesPublished by Association for Computing Machinery (ACM) ,1998
- On approximating arbitrary metrices by tree metricsPublished by Association for Computing Machinery (ACM) ,1998
- Approximation algorithms for geometric median problemsInformation Processing Letters, 1992
- An Algorithmic Approach to Network Location Problems. II: Thep-MediansSIAM Journal on Applied Mathematics, 1979
- A Heuristic Program for Locating WarehousesManagement Science, 1963