Details

Autor(en) / Beteiligte

• Gehweiler, Joachim
• Lammersen, Christiane
• Sohler, Christian

Titel

A distributed O (1)-approximation algorithm for the uniform facility location problem

Ist Teil von

• ACM Symposium on Parallel Algorithms and Architectures: Proceedings of the eighteenth annual ACM symposium on Parallelism in algorithms and architectures; 30 July-02 Aug. 2006, 2006, p.237-243

Ort / Verlag

ACM

Erscheinungsjahr

2006

Link zum Volltext

Quelle

ACM Digital Library (Association for Computing Machinery)

Beschreibungen/Notizen

• 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.