Distributed approximation algorithms for weighted shortest paths

DOI10.1145/2591796.2591850zbMATH Open1315.05136arXiv1403.5171OpenAlexW2040011014MaRDI QIDQ5259592FDOQ5259592

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)

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.

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

zbMATH Keywords

distributed computinglower boundsgraph algorithmstime complexitysingle-source shortest pathsCONGEST modelall-pairs shortest paths

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Theory of Cryptography
• The geometry of differential privacy: the small database and approximate cases
• 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
• Differential Privacy and the Fat-Shattering Dimension of Linear Queries
• Our Data, Ourselves: Privacy Via Distributed Noise Generation
• On the complexity of differentially private data release
• Collusion-secure fingerprinting for digital data
• Advances in Cryptology – CRYPTO 2004
• New Efficient Attacks on Statistical Disclosure Control Mechanisms
• Bounds on the Sample Complexity for Private Learning and Private Data Release
• Answering n _{2+o(1)} counting queries with differential privacy is hard
• Characterizing the sample complexity of private learners
• Faster Algorithms for Privately Releasing Marginals
• Faster private release of marginals on small databases
• Private Learning and Sanitization: Pure vs. Approximate Differential Privacy
• Privately releasing conjunctions and the statistical query barrier
• Efficient algorithms for privately releasing marginals via convex relaxations

Cited In (36)

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

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)