%0 Conference Paper %1 Blelloch:2010:PAA:1810479.1810535 %A Blelloch, Guy E. %A Tangwongsan, Kanat %B Proceedings of the 22nd ACM symposium on Parallelism in algorithms and architectures %C New York, NY, USA %D 2010 %I ACM %K facility.location %P 315--324 %R 10.1145/1810479.1810535 %T Parallel approximation algorithms for facility-location problems %X This paper presents the design and analysis of parallel approximation algorithms for facility-location problems, including <b>NC</b> and <b>RNC</b> algorithms for (metric) facility location, <i>k</i>-center, <i>k</i>-median, and <i>k</i>-means. These problems have received considerable attention during the past decades from the approximation algorithms community, which primarily concentrates on improving the approximation guarantees. In this paper, we ask: <i>Is it possible to parallelize some of the beautiful results from the sequential setting?</i>.</p> <p>Our starting point is a small, but diverse, subset of results in approximation algorithms for facility-location problems, with a primary goal of developing techniques for devising their efficient parallel counterparts. We focus on giving algorithms with low depth, near work efficiency (compared to the sequential versions), and low cache complexity. %@ 978-1-4503-0079-7

@inproceedings{Blelloch:2010:PAA:1810479.1810535, abstract = {This paper presents the design and analysis of parallel approximation algorithms for facility-location problems, including <b>NC</b> and <b>RNC</b> algorithms for (metric) facility location, <i>k</i>-center, <i>k</i>-median, and <i>k</i>-means. These problems have received considerable attention during the past decades from the approximation algorithms community, which primarily concentrates on improving the approximation guarantees. In this paper, we ask: <i>Is it possible to parallelize some of the beautiful results from the sequential setting?</i>.</p> <p>Our starting point is a small, but diverse, subset of results in approximation algorithms for facility-location problems, with a primary goal of developing techniques for devising their efficient parallel counterparts. We focus on giving algorithms with low depth, near work efficiency (compared to the sequential versions), and low cache complexity.}, acmid = {1810535}, added-at = {2013-02-17T19:20:16.000+0100}, address = {New York, NY, USA}, author = {Blelloch, Guy E. and Tangwongsan, Kanat}, biburl = {https://www.bibsonomy.org/bibtex/2dd304dac620c7037fc8c769e4170f660/ytyoun}, booktitle = {Proceedings of the 22nd ACM symposium on Parallelism in algorithms and architectures}, doi = {10.1145/1810479.1810535}, interhash = {b201b44a6f1c606a651a356b664fd627}, intrahash = {dd304dac620c7037fc8c769e4170f660}, isbn = {978-1-4503-0079-7}, keywords = {facility.location}, location = {Thira, Santorini, Greece}, numpages = {10}, pages = {315--324}, publisher = {ACM}, series = {SPAA '10}, timestamp = {2013-02-17T19:20:16.000+0100}, title = {Parallel approximation algorithms for facility-location problems}, year = 2010 }