%0 Conference Paper %1 814571 %A Jain, K. %A Vazirani, V.V. %B Foundations of Computer Science, 1999. 40th Annual Symposium on %D 1999 %K facility.location linear_programming primal-dual %P 2 -13 %R 10.1109/SFFCS.1999.814571 %T Primal-dual approximation algorithms for metric facility location and k-median problems %X 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

@inproceedings{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}, added-at = {2013-01-08T19:26:15.000+0100}, author = {Jain, K. and Vazirani, V.V.}, biburl = {https://www.bibsonomy.org/bibtex/26ffcf950abf42b41e4b20225c9b4eb0b/ytyoun}, booktitle = {Foundations of Computer Science, 1999. 40th Annual Symposium on}, doi = {10.1109/SFFCS.1999.814571}, interhash = {4dc7a36fb5740f359441570fc51dc82e}, intrahash = {6ffcf950abf42b41e4b20225c9b4eb0b}, issn = {0272-5428}, keywords = {facility.location linear_programming primal-dual}, pages = {2 -13}, timestamp = {2013-01-08T19:26:16.000+0100}, title = {Primal-dual approximation algorithms for metric facility location and k-median problems}, year = 1999 }