Efficient distributed approximation algorithms via probabilistic tree embeddings

DOI10.1145/1400751.1400787zbMath1301.68257OpenAlexW2100812758MaRDI QIDQ5892002

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 approximationleast element listsprobabilistic tree embeddingsgeneralized steiner forests

Mathematics Subject Classification ID

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

Related Items (4)

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

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