Distributed approximation algorithms for weighted shortest paths

DOI10.1145/2591796.2591850zbMath1315.05136arXiv1403.5171OpenAlexW2040011014MaRDI QIDQ5259592

Danupon Nanongkai

Publication date: 26 June 2015

Published in: Proceedings of the forty-sixth annual ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1403.5171

zbMATH Keywords

lower boundsgraph algorithmstime complexitydistributed computingsingle-source shortest pathsCONGEST modelall-pairs shortest paths

Mathematics Subject Classification ID

Paths and cycles (05C38) Distance in graphs (05C12) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Distributed algorithms (68W15)

Related Items (29)

Distributed finite-time calculation of node eccentricities, graph radius and graph diameter ⋮ A fast network-decomposition algorithm and its applications to constant-time distributed computation ⋮ Distributed Broadcast Revisited: Towards Universal Optimality ⋮ Fast Distributed Approximation for Max-Cut ⋮ A Fast Network-Decomposition Algorithm and Its Applications to Constant-Time Distributed Computation ⋮ Single-source shortest paths in the CONGEST model with improved bounds ⋮ Low-congestion shortcuts without embedding ⋮ Derandomizing local distributed algorithms under bandwidth restrictions ⋮ Distributed distance computation and routing with small messages ⋮ Lessons from the congested clique applied to MapReduce ⋮ A distributed algorithm for directed minimum-weight spanning tree ⋮ The sparsest additive spanner via multiple weighted BFS trees ⋮ Distributed Graph Algorithms and their Complexity: An Introduction ⋮ On efficient distributed construction of near optimal routing schemes ⋮ Algebraic methods in the congested clique ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Sparse matrix multiplication and triangle listing in the congested clique model ⋮ The Sparsest Additive Spanner via Multiple Weighted BFS Trees ⋮ Fast approximate shortest paths in the congested clique ⋮ Hopsets with Constant Hopbound, and Applications to Approximate Shortest Paths ⋮ Near-Optimal Approximate Shortest Paths and Transshipment in Distributed and Streaming Models ⋮ A Deterministic Almost-Tight Distributed Algorithm for Approximating Single-Source Shortest Paths ⋮ Linear-size hopsets with small hopbound, and constant-hopbound hopsets in RNC ⋮ Distributed Approximation Algorithms for Steiner Tree in the CONGESTED CLIQUE ⋮ Distributed Exact Weighted All-Pairs Shortest Paths in Randomized Near-Linear Time ⋮ A distributed enumeration algorithm and applications to all pairs shortest paths, diameter\dots

Uses Software

• SuLQ

Cites Work

• Unnamed Item
• Unnamed Item
• Efficient algorithms for privately releasing marginals via convex relaxations
• The Geometry of Differential Privacy: The Small Database and Approximate Cases
• Faster Algorithms for Privately Releasing Marginals
• Private Learning and Sanitization: Pure vs. Approximate Differential Privacy
• Privately Releasing Conjunctions and the Statistical Query Barrier
• On the geometry of differential privacy
• Interactive privacy via the median mechanism
• The price of privately releasing contingency tables and the spectra of random matrices with correlated rows
• Lower Bounds in Differential Privacy
• Iterative Constructions and Private Data Release
• Characterizing the sample complexity of private learners
• Faster private release of marginals on small databases
• Bounds on the Sample Complexity for Private Learning and Private Data Release
• Differential Privacy and the Fat-Shattering Dimension of Linear Queries
• Our Data, Ourselves: Privacy Via Distributed Noise Generation
• New Efficient Attacks on Statistical Disclosure Control Mechanisms
• Collusion-secure fingerprinting for digital data
• On the complexity of differentially private data release
• Advances in Cryptology – CRYPTO 2004
• Answering n _{2+o(1)} counting queries with differential privacy is hard
• Theory of Cryptography

This page was built for publication: Distributed approximation algorithms for weighted shortest paths