Title :
Primal-dual approximation algorithms for metric facility location and k-median problems
Author :
Jain, Kamal ; Vazirani, Vijay V.
Author_Institution :
Coll. of Comput., Georgia Inst. of Technol., Atlanta, GA, USA
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 :
algorithm theory; facility location; approximation algorithms; k-median problems; metric facility location; primal-dual schema; Approximation algorithms; Cities and towns; Costs; Educational institutions; Joining processes; Microwave integrated circuits; Operations research; Postal services; Upper bound;
Conference_Titel :
Foundations of Computer Science, 1999. 40th Annual Symposium on
Conference_Location :
New York City, NY
Print_ISBN :
0-7695-0409-4
DOI :
10.1109/SFFCS.1999.814571
