{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,9]],"date-time":"2026-07-09T06:02:54Z","timestamp":1783576974589,"version":"3.55.0"},"reference-count":35,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2012,1,28]],"date-time":"2012-01-28T00:00:00Z","timestamp":1327708800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Distrib. Comput."],"published-print":{"date-parts":[[2012,6]]},"DOI":"10.1007\/s00446-012-0157-9","type":"journal-article","created":{"date-parts":[[2012,1,27]],"date-time":"2012-01-27T06:06:03Z","timestamp":1327644363000},"page":"189-205","source":"Crossref","is-referenced-by-count":32,"title":["Efficient distributed approximation algorithms via probabilistic tree embeddings"],"prefix":"10.1007","volume":"25","author":[{"given":"Maleq","family":"Khan","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Fabian","family":"Kuhn","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Dahlia","family":"Malkhi","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Gopal","family":"Pandurangan","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Kunal","family":"Talwar","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2012,1,28]]},"reference":[{"issue":"2","key":"157_CR1","doi-asserted-by":"crossref","first-page":"316","DOI":"10.1006\/jagm.1993.1016","volume":"14","author":"Y. Afek","year":"1993","unstructured":"Afek Y., Ricklin M.: Sparser: a paradigm for running distributed algorithms. J. Algorithms 14(2), 316\u2013328 (1993)","journal-title":"J. Algorithms"},{"key":"157_CR2","doi-asserted-by":"crossref","unstructured":"Awerbuch, B.: Optimal distributed algorithms for minimum weight spanning tree, counting, leader election, and related problems. In: Proceedings of the 19th ACM Symposium on Theory of Computing (STOC), pp. 230\u2013240. ACM (1987)","DOI":"10.1145\/28395.28421"},{"key":"157_CR3","doi-asserted-by":"crossref","unstructured":"Bartal, Y.: Probabilistic approximations of metric spaces and its algorithmic applications. In: Proceedings of the 37th Annual Symposium on Foundations of Computer Science (FOCS), pp. 184\u2013193. IEEE Computer Society (1996)","DOI":"10.1109\/SFCS.1996.548477"},{"key":"157_CR4","doi-asserted-by":"crossref","unstructured":"Bartal, Y.: On approximating arbitrary metrics by tree metrics. In: Proceedings of the 30th ACM Symposium on Theory of Computing (STOC), pp. 161\u2013168. ACM (1998)","DOI":"10.1145\/276698.276725"},{"key":"157_CR5","doi-asserted-by":"crossref","unstructured":"Bartal, Y., Byers, J., Raz, D.: Global optimization using local information with applications to flow control. In: Proceedings of the 38th Annual Symposium on Foundations of Computer Science (FOCS), pp. 303\u2013312. IEEE Computer Society (1997)","DOI":"10.1109\/SFCS.1997.646119"},{"key":"157_CR6","doi-asserted-by":"crossref","unstructured":"Chalermsook, P., Fakcharoenphol, J.: Simple distributed algorithms for approximating minimum Steiner trees. In: Proceedings of the 11th Annual International Conference on Computing and Combinatorics (COCOON), pp. 380\u2013389. Springer (2005)","DOI":"10.1007\/11533719_39"},{"key":"157_CR7","doi-asserted-by":"crossref","unstructured":"Charikar, M., Chekuri, C., Goel, A., Guha, S., Plotkin, S.: Approximating a finite metric by a small number of tree metrics. In: Proceedings of the 39th Annual Symposium on Foundations of Computer Science (FOCS), pp. 379\u2013388. IEEE Computer Society (1998)","DOI":"10.1109\/SFCS.1998.743488"},{"issue":"3","key":"157_CR8","doi-asserted-by":"crossref","first-page":"441","DOI":"10.1006\/jcss.1997.1534","volume":"55","author":"E. Cohen","year":"1997","unstructured":"Cohen E.: Size-estimation framework with applications to transitive closure and reachability. J. Comput. Syst. Sci. 55(3), 441\u2013453 (1997)","journal-title":"J. Comput. Syst. Sci."},{"issue":"3","key":"157_CR9","doi-asserted-by":"crossref","first-page":"265","DOI":"10.1016\/j.jcss.2006.10.016","volume":"73","author":"E. Cohen","year":"2007","unstructured":"Cohen E., Kaplan H.: Spatially-decaying aggregation over a network. J. Comput. Syst. Sci. 73(3), 265\u2013288 (2007)","journal-title":"J. Comput. Syst. Sci."},{"key":"157_CR10","doi-asserted-by":"crossref","unstructured":"Sarma, A., Holzer, S., Kor, L., Korman, A., Nanongkai, D., Pandurangan, G., Peleg, D., Wattenhofer, R.: Distributed verification and hardness of distributed approximation. In: Proceedings of the 43rd ACM Symposium on Theory of Computing (STOC), pp. 363\u2013372. ACM (2011)","DOI":"10.1145\/1993636.1993686"},{"key":"157_CR11","unstructured":"Dubhashi, D., Grandioni, F., Panconesi, A.: Distributed approximation algorithms via LP duality and randomization. In: Gonzalez T. (ed.) Handbook of Approximation Algorithms and Metaheuristics, CRC Press, Boca Raton (2007)"},{"issue":"2","key":"157_CR12","doi-asserted-by":"crossref","first-page":"283","DOI":"10.1145\/1103963.1103968","volume":"1","author":"M. Elkin","year":"2005","unstructured":"Elkin M.: Computing almost shortest paths. ACM Trans. Algorithms 1(2), 283\u2013322 (2005)","journal-title":"ACM Trans. Algorithms"},{"issue":"4","key":"157_CR13","doi-asserted-by":"crossref","first-page":"40","DOI":"10.1145\/1054916.1054931","volume":"35","author":"M. Elkin","year":"2004","unstructured":"Elkin M.: Distributed approximation: a survey. ACM SIGACT News 35(4), 40\u201357 (2004)","journal-title":"ACM SIGACT News"},{"issue":"8","key":"157_CR14","doi-asserted-by":"crossref","first-page":"1282","DOI":"10.1016\/j.jcss.2006.07.002","volume":"72","author":"M. Elkin","year":"2006","unstructured":"Elkin M.: A faster distributed protocol for constructing a minimum spanning tree. J. Comput. Syst. Sci. 72(8), 1282\u20131308 (2006)","journal-title":"J. Comput. Syst. Sci."},{"issue":"2","key":"157_CR15","doi-asserted-by":"crossref","first-page":"433","DOI":"10.1137\/S0097539704441058","volume":"36","author":"M. Elkin","year":"2006","unstructured":"Elkin M.: An unconditional lower bound on the time-approximation tradeoff for the minimum spanning tree problem. SIAM J. Comput. 36(2), 433\u2013456 (2006)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"157_CR16","doi-asserted-by":"crossref","first-page":"485","DOI":"10.1016\/j.jcss.2004.04.011","volume":"69","author":"J. Fakcharoenphol","year":"2004","unstructured":"Fakcharoenphol J., Rao S., Talwar K.: A tight bound on approximating arbitrary metrics by tree metrics. J. Comput. Syst. Sci. 69(3), 485\u2013497 (2004)","journal-title":"J. Comput. Syst. Sci."},{"issue":"1","key":"157_CR17","doi-asserted-by":"crossref","first-page":"66","DOI":"10.1145\/357195.357200","volume":"5","author":"R. Gallager","year":"1983","unstructured":"Gallager R., Humblet P., Spira P.: A distributed algorithm for minimum-weight spanning trees. ACM Trans. Program. Lang. Syst. 5(1), 66\u201377 (1983)","journal-title":"ACM Trans. Program. Lang. Syst."},{"key":"157_CR18","doi-asserted-by":"crossref","unstructured":"Grandoni, F., K\u00f6nemann, J., Panconesi, A., Sozio, M.: Primal-dual based distributed algorithms for vertex cover with semi-hard capacities. In: Proceedings of the 24th ACM symposium on Principles of distributed computing (PODC), pp. 118-125. ACM (2005)","DOI":"10.1145\/1073814.1073835"},{"issue":"4","key":"157_CR19","doi-asserted-by":"crossref","first-page":"193","DOI":"10.1007\/s00446-002-0078-0","volume":"15","author":"L. Jia","year":"2002","unstructured":"Jia L., Rajaraman R., Suel R.: An efficient distributed algorithm for constructing small dominating sets. Distrib. Comput. 15(4), 193\u2013205 (2002)","journal-title":"Distrib. Comput."},{"key":"157_CR20","doi-asserted-by":"crossref","first-page":"391","DOI":"10.1007\/s00446-007-0047-8","volume":"20","author":"M. Khan","year":"2008","unstructured":"Khan M., Pandurangan G.: A fast distributed approximation algorithm for minimum spanning trees. Distrib. Comput. 20, 391\u2013402 (2008)","journal-title":"Distrib. Comput."},{"key":"157_CR21","doi-asserted-by":"crossref","unstructured":"Kuhn, F., Moscibroda, T., Wattenhofer, R.: What cannot be computed locally! In: Proceedings of the 23rd ACM symposium on Principles of distributed computing (PODC), pp. 300\u2013309. ACM (2004)","DOI":"10.1145\/1011767.1011811"},{"key":"157_CR22","doi-asserted-by":"crossref","unstructured":"Kuhn, F., Moscibroda, T., Wattenhofer, R.: The price of being near-sighted. In: Proceedings of the 17th ACM-SIAM Symposium on Discrete Algorithms (SODA). pp. 980\u2013989. SIAM (2006)","DOI":"10.1145\/1109557.1109666"},{"key":"157_CR23","doi-asserted-by":"crossref","first-page":"40","DOI":"10.1006\/jagm.1998.0929","volume":"28","author":"S. Kutten","year":"1998","unstructured":"Kutten S., Peleg D.: Fast distributed construction of k-dominating sets and applications. J. Algorithms 28, 40\u201366 (1998)","journal-title":"J. Algorithms"},{"key":"157_CR24","unstructured":"Nutov, Z., Sadeh, A.: Distributed primal-dual approximation algorithms for network design problems. Manuscript, (2009). http:\/\/www.openu.ac.il\/home\/nutov\/distributed.pdf"},{"key":"157_CR25","doi-asserted-by":"crossref","first-page":"350","DOI":"10.1137\/S0097539793250767","volume":"26","author":"A. Panconesi","year":"1997","unstructured":"Panconesi A., Srinivasan A.: Randomized distributed edge coloring via an extension of the Chernoff-Hoeffding bounds. SIAM J. Comput. 26, 350\u2013368 (1997)","journal-title":"SIAM J. Comput."},{"key":"157_CR26","volume-title":"Algorithms and Theory of Computation Handbook.","author":"G. Pandurangan","year":"2009","unstructured":"Pandurangan G., Khan M.: Theory of communication networks. In: Atallah, M.J., Blanton, M. (eds) Algorithms and Theory of Computation Handbook., CRC Press, Boca Raton (2009)"},{"key":"157_CR27","doi-asserted-by":"crossref","unstructured":"Papadimitriou, C., Yannakakis, M.: Linear programming without matrix. In: Proceedings of the 25th ACM Symposium on Theory of Computing (STOC), pp. 121-129, ACM (1993)","DOI":"10.1145\/167088.167127"},{"key":"157_CR28","doi-asserted-by":"crossref","first-page":"96","DOI":"10.1016\/0743-7315(90)90074-Y","volume":"8","author":"D. Peleg","year":"1990","unstructured":"Peleg D.: A time optimal leader election algorithm in general networks. J. Parallel Distrib. Comput. 8, 96\u201399 (1990)","journal-title":"J. Parallel Distrib. Comput."},{"key":"157_CR29","doi-asserted-by":"crossref","unstructured":"Peleg D.: Distributed Computing: A Locality-Sensitive Approach. SIAM, (2000)","DOI":"10.1137\/1.9780898719772"},{"key":"157_CR30","unstructured":"Peleg, D., Rabinovich, V.: A near-tight lower bound on the time complexity of distributed mst construction. In: Proceedings of the 40th Annual Symposium on Foundations of Computer Science (FOCS), pp. 379\u2013388. IEEE Computer Society (1999)"},{"key":"157_CR31","doi-asserted-by":"crossref","DOI":"10.1007\/BFb0020419","volume-title":"Introduction to Distributed Algorithms","author":"G. Tel","year":"1994","unstructured":"Tel G.: Introduction to Distributed Algorithms. Cambridge University Press, Cambridge (1994)"},{"key":"157_CR32","volume-title":"Approximation Algorithms","author":"V. Vazirani","year":"2004","unstructured":"Vazirani V.: Approximation Algorithms. Springer, New York (2004)"},{"key":"157_CR33","doi-asserted-by":"crossref","unstructured":"Wattenhofer, M., Wattenhofer, R.: Distributed weighted matching. In: Proceedings of the 18th Conference on Distributed Computing (DISC), pp. 335\u2013348. Springer, New York (2004)","DOI":"10.1007\/978-3-540-30186-8_24"},{"key":"157_CR34","doi-asserted-by":"crossref","DOI":"10.1201\/9780203497289","volume-title":"Spanning Trees and Optimization Problems","author":"B. Wu","year":"2004","unstructured":"Wu B., Chao K.: Spanning Trees and Optimization Problems. Chapman and Hall\/CRC, Boca Raton (2004)"},{"key":"157_CR35","unstructured":"Wu, B., Lancia, G., Bafna, V., Chao, K., Ravi, R., Tang, C.: A polynomial time approximation scheme for minimum routing cost spanning trees. In: Proceedings of the 9th ACM-SIAM Symposium on Discrete Algorithms (SODA). pp. 21\u201332. SIAM (1998)"}],"container-title":["Distributed Computing"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00446-012-0157-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00446-012-0157-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00446-012-0157-9","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,19]],"date-time":"2025-03-19T09:24:21Z","timestamp":1742376261000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00446-012-0157-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,1,28]]},"references-count":35,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2012,6]]}},"alternative-id":["157"],"URL":"https:\/\/doi.org\/10.1007\/s00446-012-0157-9","relation":{},"ISSN":["0178-2770","1432-0452"],"issn-type":[{"value":"0178-2770","type":"print"},{"value":"1432-0452","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,1,28]]}}}