Efficient distributed approximation algorithms via probabilistic tree embeddings

DOI10.1007/S00446-012-0157-9zbMath1259.68228OpenAlexW2027018686MaRDI QIDQ5917892

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

Publication date: 4 February 2013

Published in: Distributed Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00446-012-0157-9

zbMATH Keywords

metric spacesshortest pathsleader electiongeneralized Steiner forestsleast element listsoptimum routing cost spanning treesprobabilistic tree embeddings

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Data structures (68P05) Approximation algorithms (68W25) Distributed algorithms (68W15)

Related Items (9)

Metric Embedding via Shortest Path Decompositions ⋮ Fast Distributed Approximation for TAP and 2-Edge-Connectivity ⋮ Prioritized Metric Structures and Embedding ⋮ Improved deterministic leader election in diameter-two networks ⋮ Decentralized Low-Stretch Trees via Low Diameter Graph Decompositions ⋮ Fast distributed approximation for TAP and 2-edge-connectivity ⋮ The complexity of leader election in diameter-two networks ⋮ A Deterministic Almost-Tight Distributed Algorithm for Approximating Single-Source Shortest Paths ⋮ On the Complexity of Universal Leader Election

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Quantum mechanical algorithms for the nonabelian hidden subgroup problem
• A faster distributed protocol for constructing a minimum spanning tree
• Spatially-decaying aggregation over a network
• Size-estimation framework with applications to transitive closure and reachability
• A fast distributed approximation algorithm for minimum spanning trees
• An Unconditional Lower Bound on the Time-Approximation Trade-off for the Distributed Minimum Spanning Tree Problem
• The price of being near-sighted
• A Distributed Algorithm for Minimum-Weight Spanning Trees
• Sparser: A Paradigm for Running Distributed Algorithms
• Fast Distributed Construction of Smallk-Dominating Sets and Applications
• Randomized Distributed Edge Coloring via an Extension of the Chernoff--Hoeffding Bounds
• Distributed Computing: A Locality-Sensitive Approach
• Primal-dual based distributed algorithms for vertex cover with semi-hard capacities
• Linear programming without the matrix
• Distributed verification and hardness of distributed approximation
• Distributed Weighted Matching
• What cannot be computed locally!
• Computing and Combinatorics
• Computing almost shortest paths
• A tight bound on approximating arbitrary metrics by tree metrics

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