Parallel probabilistic tree embeddings, k-median, and buy-at-bulk network design

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(n ² log n) work and O(log ² n) depth - these bounds are independent of Δ = max _x,y d(x,y)/min _x≠y d(x;y), the ratio of the largest to smallest distance. Moreover, when Δ is exponentially bounded (Δ ≤/2 ^O(n)), our algorithm can be improved to O(n ²) work and O(log ² n) depth. Using these results, we give an RNC O(log κ)-approximation algorithm for κ-median and an RNC O(log n)-approximation for buy-at-bulk network design. The κ-median algorithm is the first RNC algorithm with non-trivial guarantees for arbitrary values of κ, and the buy-at-bulk result is the first parallel algorithm for the problem.