Efficient distributed approximation algorithms via probabilistic tree embeddings

DOI10.1145/1400751.1400787zbMATH Open1301.68257OpenAlexW2100812758MaRDI QIDQ5892002FDOQ5892002

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

Publication date: 12 December 2014

Published in: Proceedings of the twenty-seventh ACM symposium on Principles of distributed computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/1400751.1400787

zbMATH Keywords

metric spacesnetwork optimizationdistributed approximationprobabilistic tree embeddingsgeneralized steiner forestsleast element lists

Mathematics Subject Classification ID

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

Cited In (5)

• Primal-dual based distributed approximation algorithm for Prize-collecting Steiner tree
• Distributed Approximation Algorithms for Steiner Tree in the CONGESTED CLIQUE
• Efficient distributed computation of distance sketches in networks
• Singularly optimal randomized leader election
• Sublinear bounds for randomized leader election

This page was built for publication: Efficient distributed approximation algorithms via probabilistic tree embeddings

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5892002)