Primal-dual approximation algorithms for metric facility location and k-median problems
- 20 January 2003
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- Vol. 1412 (02725428) , 2-13
- https://doi.org/10.1109/sffcs.1999.814571
Abstract
We present approximation algorithms for the metric uncapacitated facility location problem and the metric k-median problem achieving guarantees of 3 and 6 respectively. The distinguishing feature of our algorithms is their low running time: O(m log m) and O(m log m(L+log(n))) respectively, where n and m are the total number of vertices and edges in the underlying graph. The main algorithmic idea is a new extension of the primal-dual schema.Keywords
This publication has 19 references indexed in Scilit:
- Probabilistic approximation of metric spaces and its algorithmic applicationsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Greedy Strikes Back: Improved Facility Location AlgorithmsJournal of Algorithms, 1999
- Improved Approximation Algorithms for Uncapacitated Facility LocationPublished by Springer Nature ,1998
- An approximation algorithm for minimum-cost vertex-connectivity problemsAlgorithmica, 1997
- A primal-dual approximation algorithm for generalized steiner network problemsCombinatorica, 1995
- A General Approximation Technique for Constrained Forest ProblemsSIAM Journal on Computing, 1995
- How to Allocate Network CentersJournal of Algorithms, 1993
- A linear-time approximation algorithm for the weighted vertex cover problemJournal of Algorithms, 1981
- Maximum matching and a polyhedron with 0,1-verticesJournal of Research of the National Bureau of Standards Section B Mathematics and Mathematical Physics, 1965
- A Working Model for Plant Numbers and LocationsJournal of Farm Economics, 1963