TY - GEN

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

AU - Blelloch, Guy E.

AU - Gupta, Anupam

AU - Tangwongsan, Kanat

PY - 2012

Y1 - 2012

N2 - 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 2 log n) work and O(log 2 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 2) work and O(log 2 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.

AB - 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 2 log n) work and O(log 2 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 2) work and O(log 2 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.

KW - Buy-at-bulk network design

KW - K-median

KW - Parallel algorithms

KW - Probabilistic tree embedding

UR - http://www.scopus.com/inward/record.url?scp=84864148744&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84864148744&partnerID=8YFLogxK

U2 - 10.1145/2312005.2312045

DO - 10.1145/2312005.2312045

M3 - Conference contribution

AN - SCOPUS:84864148744

SN - 9781450312134

T3 - Annual ACM Symposium on Parallelism in Algorithms and Architectures

SP - 205

EP - 213

BT - SPAA'12 - Proceedings of the 24th ACM Symposium on Parallelism in Algorithms and Architectures

T2 - 24th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA'12

Y2 - 25 June 2012 through 27 June 2012

ER -