Fast partial distance estimation and applications

DOI10.1145/2767386.2767398MaRDI QIDQ2796252zbMATH OpenOpenAlexFDO

Authors Christoph Lenzen, Boaz Patt-Shamir

Publication date 23 March 2016

Published in Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing (Search for Journal in Brave)

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

zbMATH Keywords

congest modelrouting table constructionsource detectionSteiner forestsweighted all-pairs shortest paths

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Distributed algorithms (68W15) Randomized algorithms (68W20) Approximation algorithms (68W25)

Abstract: We study approximate distributed solutions to the weighted {it all-pairs-shortest-paths} (APSP) problem in the CONGEST model. We obtain the following results. $1.$ A deterministic $(1+o(1))$-approximation to APSP in $ildeO(n)$ rounds. This improves over the best previously known algorithm, by both derandomizing it and by reducing the running time by a $Theta(logn)$ factor. In many cases, routing schemes involve relabeling, i.e., assigning new names to nodes and require that these names are used in distance and routing queries. It is known that relabeling is necessary to achieve running times of $o(n/logn)$. In the relabeling model, we obtain the following results. $2.$ A randomized $O(k)$-approximation to APSP, for any integer $k>1$, running in $ildeO(n^{1/2+1/k}+D)$ rounds, where $D$ is the hop diameter of the network. This algorithm simplifies the best previously known result and reduces its approximation ratio from $O(klogk)$ to $O(k)$. Also, the new algorithm uses uses labels of asymptotically optimal size, namely $O(logn)$ bits. $3.$ A randomized $O(k)$-approximation to APSP, for any integer $k>1$, running in time $ildeO((nD{)}^{1/2}cdot{n}^{1/k}+D)$ and producing {it compact routing tables} of size $ildeO(n^{1/k})$. The node lables consist of $O(klogn)$ bits. This improves on the approximation ratio of $Theta(k^2)$ for tables of that size achieved by the best previously known algorithm, which terminates faster, in $ildeO(n^{1/2+1/k}+D)$ rounds.

Recommendations

• Fast routing table construction using small messages (extended abstract)
• Distributed approximation algorithms for weighted shortest paths
• Fast approximate shortest paths in the congested clique
• Approximation of distances and shortest paths in the broadcast congest clique
• A deterministic almost-tight distributed algorithm for approximating single-source shortest paths

Cites work

• scientific article; zbMATH DE number 826255 (Why is no real title available?)
• Memorization and Association on a Realistic Neural Model

Cited in

(18)

• Fast FILTERSIM simulation with score-based distance
• Fast spatial decomposition and closest pair computation for limited precision input
• 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
• Distributed distance computation and routing with small messages
• Accuracy and fidelity of fast net length estimates
• A deterministic almost-tight distributed algorithm for approximating single-source shortest paths
• Primal-dual based distributed approximation algorithm for Prize-collecting Steiner tree
• Distributed Exact Weighted All-Pairs Shortest Paths in Randomized Near-Linear Time
• Faster distributed shortest path approximations via shortcuts
• Hopsets with constant hopbound, and applications to approximate shortest paths
• Efficient minimum distance estimation with multiple rates of convergence
• Fast routing table construction using small messages (extended abstract)
• Distributed approximation algorithms for Steiner tree in the CONGESTED CLIQUE
• Distributed planar reachability in nearly optimal time
• Distance computations in the hybrid network model via oracle simulations

This page was built for publication: Fast partial distance estimation and applications

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