Parallel probabilistic tree embeddings, k-median, and buy-at-bulk network design
Guy E. Blelloch, Anupam Gupta, Kanat Tangwongsan · 2012
This paper presents parallel algorithms for embedding an arbitrary n-point metric space into a distribution of dominating trees with O(log n) expected stretch. Such embedding has proved useful in the design of many approximation algorithms in the sequential setting. We give a parallel algorithm that runs in O(n2 log n) work and O(log2 n) depth---these bounds are independent of Δ = (maxx,y d(x,y))/(minx≠ y d(x,y)), the ratio of the largest to smallest distance. Moreover, when Δ is exponentially bounded (Δ ≤ 2O(n)), our algorithm can be improved to O(n2) work and O(log2 n) depth. Using these results, we give an RNC O(log k)-approximation algorithm for k-median and an RNC O(log n)-approximation for buy-at-bulk network design. The k-median algorithm is the first RNC algorithm with non-trivial guarantees for arbitrary values of k, and the buy-at-bulk result is the first parallel algorithm for the problem.