Distributed approximation algorithms for weighted shortest paths

DOI10.1145/2591796.2591850MaRDI QIDQ5259592zbMATH OpenOpenAlexFDO

Authors 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

all-pairs shortest pathsCONGEST modeldistributed computinggraph algorithmslower boundssingle-source shortest pathstime complexity

Mathematics Subject Classification ID

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

Abstract: A distributed network is modeled by a graph having $n$ nodes (processors) and diameter $D$. We study the time complexity of approximating {em weighted} (undirected) shortest paths on distributed networks with a $O(logn)$ {em bandwidth restriction} on edges (the standard synchronous congest model). The question whether approximation algorithms help speed up the shortest paths (more precisely distance computation) was raised since at least 2004 by Elkin (SIGACT News 2004). The unweighted case of this problem is well-understood while its weighted counterpart is fundamental problem in the area of distributed approximation algorithms and remains widely open. We present new algorithms for computing both single-source shortest paths (sssp) and all-pairs shortest paths (apsp) in the weighted case. Our main result is an algorithm for sssp. Previous results are the classic $O(n)$-time Bellman-Ford algorithm and an $ildeO(n^{1/2+1/2k}+D)$-time $(8klceillog(k+1)ceil-1)$-approximation algorithm, for any integer $kgeq1$, which follows from the result of Lenzen and Patt-Shamir (STOC 2013). (Note that Lenzen and Patt-Shamir in fact solve a harder problem, and we use $ildeO(cdot)$ to hide the $O(polylogn)$ term.) We present an $ildeO(n^{1/2}{D}^{1/4}+D)$-time $(1+o(1))$-approximation algorithm for sssp. This algorithm is {em sublinear-time} as long as $D$ is sublinear, thus yielding a sublinear-time algorithm with almost optimal solution. When $D$ is small, our running time matches the lower bound of $ildeOmega(n^{1/2}+D)$ by Das Sarma et al. (SICOMP 2012), which holds even when $D=Theta(logn)$, up to a $polylogn$ factor.

Recommendations

• A deterministic almost-tight distributed algorithm for approximating single-source shortest paths
• A deterministic almost-tight distributed algorithm for approximating single-source shortest paths
• Improved distributed algorithms for exact shortest paths
• Distributed exact weighted all-pairs shortest paths in near-linear time

Cites work

• Advances in Cryptology – CRYPTO 2004
• Answering \(n^{2+o(1)}\) counting queries with differential privacy is hard
• Bounds on the sample complexity for private learning and private data release
• Characterizing the sample complexity of private learners
• Collusion-secure fingerprinting for digital data
• Differential privacy and the fat-shattering dimension of linear queries
• Efficient algorithms for privately releasing marginals via convex relaxations
• Faster algorithms for privately releasing marginals
• Faster private release of marginals on small databases
• scientific article; zbMATH DE number 5485440 (Why is no real title available?)
• scientific article; zbMATH DE number 5485574 (Why is no real title available?)
• Interactive privacy via the median mechanism
• Iterative Constructions and Private Data Release
• Lower bounds in differential privacy
• New Efficient Attacks on Statistical Disclosure Control Mechanisms
• On the complexity of differentially private data release, efficient algorithms and hardness results
• On the geometry of differential privacy
• Our Data, Ourselves: Privacy Via Distributed Noise Generation
• Private Learning and Sanitization: Pure vs. Approximate Differential Privacy
• The price of privately releasing contingency tables and the spectra of random matrices with correlated rows
• Theory of Cryptography

Cited in

(49)

• A fast network-decomposition algorithm and its applications to constant-time distributed computation
• On efficient distributed construction of near optimal routing schemes
• Fast approximate shortest paths in the congested clique
• Linear-size hopsets with small hopbound, and constant-hopbound hopsets in RNC
• Single-source shortest paths in the CONGEST model with improved bounds
• Derandomizing local distributed algorithms under bandwidth restrictions
• The sparsest additive spanner via multiple weighted BFS trees
• Sparse matrix multiplication and triangle listing in the congested clique model
• Distributed distance computation and routing with small messages
• A distributed enumeration algorithm and applications to all pairs shortest paths, diameter\dots
• Low-congestion shortcuts without embedding
• A distributed algorithm for directed minimum-weight spanning tree
• Fast partial distance estimation and applications
• Distributed finite-time calculation of node eccentricities, graph radius and graph diameter
• Optimal distributed all pairs shortest paths and applications
• Distributed Broadcast Revisited: Towards Universal Optimality
• A fast network-decomposition algorithm and its applications to constant-time distributed computation (extended abstract)
• Another adaptive distributed shortest path algorithm
• Near-Optimal Approximate Shortest Paths and Transshipment in Distributed and Streaming Models
• A deterministic almost-tight distributed algorithm for approximating single-source shortest paths
• Distributed Exact Weighted All-Pairs Shortest Paths in Randomized Near-Linear Time
• Fast Distributed Approximation for Max-Cut
• Distributed MST and broadcast with fewer messages, and faster gossiping
• Faster distributed shortest path approximations via shortcuts
• Sparse matrix multiplication and triangle listing in the congested clique model
• Large-scale distributed algorithms for facility location with outliers
• The Sparsest Additive Spanner via Multiple Weighted BFS Trees
• Distributed graph algorithms and their complexity: an introduction
• A deterministic distributed algorithm for exact weighted all-pairs shortest paths in \(\tilde{O}(n^{3/2})\) rounds
• Distributed exact weighted all-pairs shortest paths in near-linear time
• Hopsets with constant hopbound, and applications to approximate shortest paths
• Distributed Weight Balancing Over Digraphs
• A deterministic almost-tight distributed algorithm for approximating single-source shortest paths
• Approximation of distances and shortest paths in the broadcast congest clique
• Fast routing table construction using small messages (extended abstract)
• Single-Source Shortest Paths in the CONGEST Model with Improved Bound
• Distributed approximation algorithms for Steiner tree in the CONGESTED CLIQUE
• Near-optimal approximate shortest paths and transshipment in distributed and streaming models
• Reachability and shortest paths in the broadcast CONGEST model
• Finding a small vertex cut on distributed networks
• Distributed planar reachability in nearly optimal time
• Distributed distance approximation
• Distributed model checking on graphs of bounded treedepth
• Tight bounds on the message complexity of distributed tree verification
• A near-optimal low-energy deterministic distributed SSSP with ramifications on congestion and APSP
• Computing minimum weight cycle in the CONGEST model
• Distance computations in the hybrid network model via oracle simulations
• Polylogarithmic time algorithms for shortest path forests in programmable matter
• Lessons from the congested clique applied to MapReduce

Describes a project that uses

Uses Software

• SuLQ

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

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