Super-Fast Distributed Algorithms for Metric Facility Location

Andrew Berns, James Hegeman, Sriram V. Pemmaraju

This paper presents a distributed O(1)-approximation algorithm, with expected-$O(\log \log n)$ running time, in the $\mathcal{C}\mathcal{O}\mathcal{N}\mathcal{GE}\mathcal{S}\mathcal{T}$ model for the metric facility location probl…