×
Khan, Maleq; Kuhn, Fabian; Malkhi, Dahlia; Pandurangan, Gopal; Talwar, Kunal

Efficient distributed approximation algorithms via probabilistic tree embeddings. (English) Zbl 1301.68257

Proceedings of the 27th annual ACM symposium on principles of distributed computing, PODC ’08, Toronto, Canada, August 18–21, 2008. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-59593-989-0). 263-272 (2008).

Cited in 1 Review
Cited in 8 Documents

MSC:

68W15 Distributed algorithms
05C05 Trees
05C12 Distance in graphs
05C60 Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.)
05C85 Graph algorithms (graph-theoretic aspects)
68M14 Distributed systems
68W25 Approximation algorithms
90C35 Programming involving graphs or networks

Keywords:

distributed approximation; generalized steiner forests; least element lists; metric spaces; network optimization; probabilistic tree embeddings

Citations:

Zbl 1071.68082
Cite Review PDF
Full Text: DOI

References:

[1] B. Awerbuch. Optimal distributed algorithms for minimum weight spanning tree, counting, leader election, and related problems. In 19th STOC, 1987. 10.1145/28395.28421
[2] P. Chalermsook and J. Fakcharoenphol. Simple distributed algorithms for approximating minimum steiner trees. In 11th COCOON, 2005. 10.1007/11533719_39
[3] E. Cohen. Size-estimation framework with applications to transitive closure and reachability. JCSS, 55(3):441-453, 1997. 10.1006/jcss.1997.1534 · Zbl 0897.68075
[4] E. Cohen and H. Kaplan. Spatially-decaying aggregation over a network. JCSS, 73(3):265-288, 2007. 10.1016/j.jcss.2006.10.016 · Zbl 1115.68016
[5] D. Dubhashi, F. Grandioni, and A. Panconesi. Distributed algorithms via lp duality and randomization. In Handbook of Approximation Algorithms and Metaheuristics. 2007.
[6] M. Elkin. Computing almost shortest paths. In 20th PODC, 2001. 10.1145/383962.383983
[7] M. Elkin. Distributed approximation - a survey. ACM SIGACT News, 35(4):40-57, 2004. 10.1145/1054916.1054931
[8] M. Elkin. A faster distributed protocol for constructing minimum spanning tree. In 15th SODA, 2004.
[9] M. Elkin. Unconditional lower bounds on the time-approximation tradeoffs for the distributed minimum spanning tree problem. In 36th STOC, 2004. 10.1145/1007352.1007407 · Zbl 1192.68319
[10] J. Fakcharoenphol, S. Rao, and K. Talwar. A tight bound on approximating arbitrary metrics by tree metrics. JCSS, 69(3):485-497, 2004. 10.1016/j.jcss.2004.04.011 · Zbl 1071.68082
[11] R. Gallager, P. Humblet, and P. Spira. A distributed algorithm for minimum-weight spanning trees. ACM Trans. on Programming Languages and Systems, 5(1):66-77, 1983. 10.1145/357195.357200 · Zbl 0498.68040
[12] J. Garay, S. Kutten, and D. Peleg. A sublinear time distributed algorithm for minimum-weight spanning trees. SIAM J. on Computing, 27:302-316, 1998. 10.1137/S0097539794261118 · Zbl 0911.05052
[13] F. Grandoni, J. Könemann, A. Panconesi, and M. Sozio. Primal-dual based distributed algorithms for vertex cover with semi-hard capacities. In 24th PODC, 2005. 10.1145/1073814.1073835 · Zbl 1314.68156
[14] L. Jia, R. Rajaraman, and R. Suel. An efficient distributed algorithm for constructing small dominating sets. Distributed Computing, 15(4):193-205, 2002. 10.1017/s00446-002-0078-0 · Zbl 1448.68472
[15] M. Khan and G. Pandurangan. A fast distributed approximation algorithm for minimum spanning trees. Distributed Computing, 20:391-402, 2008. · Zbl 1266.68214
[16] F. Kuhn and T. Moscibroda. Distributed Approximation of Capacitated Dominating Sets. In 19th SPAA, 2007. 10.1145/1248377.1248403
[17] F. Kuhn, T. Moscibroda, and R. Wattenhofer. What Cannot Be Computed Locally! In 23rd PODC, 2004. 10.1145/1011767.1011811
[18] F. Kuhn, T. Moscibroda, and R. Wattenhofer. The Price of Being Near-Sighted. In 17th SODA, 2006. 10.1145/1109557.1109666
[19] S. Kutten and D. Peleg. Fast distributed construction of k-dominating sets and applications. J. Algorithms, 28:40-66, 1998. 10.1006/jagm.1998.0929 · Zbl 0919.68052
[20] D. Peleg. A time optimal leader election algorithm in general networks. J. Parallel and Distributed Computing, 8:96-99, 1990. 10.1016/0743-7315(90)90074-Y
[21] D. Peleg. Distributed Computing: A Locality-Sensitive Approach. SIAM, 2000. · Zbl 0959.68042
[22] D. Peleg and V. Rabinovich. A near-tight lower bound on the time complexity of distributed mst construction. In 40th FOCS, 1999.
[23] V. Vazirani. Approximation Algorithms. Springer Verlag, 2004.
[24] B. Wu, G. Lancia, V. Bafna, K. Chao, R. Ravi, and C. Tang. A polynomial time approximation scheme for minimum routing cost spanning trees. In 9th SODA, 1998.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.