A Distributed O(1)-Approximation Algorithm for the Uniform Facility Location Problem

C. Sohler, J. Gehweiler, C. Lammersen, in: Proceeedings of 18th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2006.

Download
No fulltext has been uploaded.
Conference Paper | English
Author
; ;
Abstract
In this paper, we present a randomized constant factor approximation algorithm for the metric minimum facility location problem with uniform costs and demands in a distributed setting, in which every point can open a facility. In particular, our distributed algorithm uses three communication rounds with message sizes bounded to O(log n) bits where n is the number of points. We also extend our algorithm to constant powers of metric spaces, where we also obtain a randomized constant factor approximation algorithm.
Publishing Year
Proceedings Title
Proceeedings of 18th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)
LibreCat-ID

Cite this

Sohler C, Gehweiler J, Lammersen C. A Distributed O(1)-Approximation Algorithm for the Uniform Facility Location Problem. In: Proceeedings of 18th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA). ; 2006.
Sohler, C., Gehweiler, J., & Lammersen, C. (2006). A Distributed O(1)-Approximation Algorithm for the Uniform Facility Location Problem. In Proceeedings of 18th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA).
@inproceedings{Sohler_Gehweiler_Lammersen_2006, title={A Distributed O(1)-Approximation Algorithm for the Uniform Facility Location Problem}, booktitle={Proceeedings of 18th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)}, author={Sohler, Christian and Gehweiler, Joachim and Lammersen, Christiane}, year={2006} }
Sohler, Christian, Joachim Gehweiler, and Christiane Lammersen. “A Distributed O(1)-Approximation Algorithm for the Uniform Facility Location Problem.” In Proceeedings of 18th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2006.
C. Sohler, J. Gehweiler, and C. Lammersen, “A Distributed O(1)-Approximation Algorithm for the Uniform Facility Location Problem,” in Proceeedings of 18th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2006.
Sohler, Christian, et al. “A Distributed O(1)-Approximation Algorithm for the Uniform Facility Location Problem.” Proceeedings of 18th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2006.

Export

Marked Publications

Open Data LibreCat

Search this title in

Google Scholar