Distributed Spanner Approximation

DOI10.1145/3212734.3212758MaRDI QIDQ5197675zbMATH OpenOpenAlexWikidataFDO

Authors Keren Censor-Hillel, Michal Dory

Publication date 19 September 2019

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

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

zbMATH Keywords

approximation algorithmshardness of approximationspannersdistributed network design

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Distributed algorithms (68W15)

Abstract: We address the fundamental network design problem of constructing approximate minimum spanners. Our contributions are for the distributed setting, providing both algorithmic and hardness results. Our main hardness result shows that an $alpha$-approximation for the minimum directed $k$-spanner problem for $kgeq5$ requires $Omega(n/sqrtalphalogn)$ rounds using deterministic algorithms or $Omega(sqrtn/sqrtalphalogn)$ rounds using randomized ones, in the CONGEST model of distributed computing. Combined with the constant-round $O(n^{epsilon})$-approximation algorithm in the LOCAL model of [Barenboim, Elkin and Gavoille, 2016], as well as a polylog-round $(1+epsilon)$-approximation algorithm in the LOCAL model that we show here, our lower bounds for the CONGEST model imply a strict separation between the LOCAL and CONGEST models. Notably, to the best of our knowledge, this is the first separation between these models for a local approximation problem. Similarly, a separation between the directed and undirected cases is implied. We also prove a nearly-linear lower bound for the minimum weighted $k$-spanner problem for $kgeq4$, and we show lower bounds for the weighted 2-spanner problem. On the algorithmic side, apart from the aforementioned $(1+epsilon)$-approximation algorithm for minimum $k$-spanners, our main contribution is a new distributed construction of minimum 2-spanners that uses only polynomial local computations. Our algorithm has a guaranteed approximation ratio of $O(log(m/n))$ for a graph with $n$ vertices and $m$ edges, which matches the best known ratio for polynomial time sequential algorithms [Kortsarz and Peleg, 1994], and is tight if we restrict ourselves to polynomial local computations. Our approach allows us to extend our algorithm to work also for the directed, weighted, and client-server variants of the problem.

Recommendations

• Distributed spanner approximation
• Fast deterministic distributed algorithms for sparse spanners
• Fast Deterministic Distributed Algorithms for Sparse Spanners
• Distributed algorithms for ultrasparse spanners and linear size skeletons
• Distributed algorithms for ultrasparse spanners and linear size skeletons
• On the locality of distributed sparse spanner construction
• Improved deterministic distributed construction of spanners
• A near-optimal distributed fully dynamic algorithm for maintaining sparse spanners
• Simple distributed spanners in dense congest networks

Cited in

(13)

• Sparser: A Paradigm for Running Distributed Algorithms
• Distributed construction of low-interference spanners
• Distributed spanner approximation
• The sparsest additive spanner via multiple weighted BFS trees
• Distributed distance approximation
• Constant-round spanners and shortest paths in congested clique and MPC
• The Sparsest Additive Spanner via Multiple Weighted BFS Trees
• Distributed algorithms for ultrasparse spanners and linear size skeletons
• Distributed Approximation of Minimum k-edge-connected Spanning Subgraphs
• The message complexity of distributed graph optimization
• Distributed distance-bounded network design through distributed convex programming
• scientific article; zbMATH DE number 2036580 (Why is no real title available?)
• Distribution-sensitive construction of the greedy spanner

This page was built for publication: Distributed Spanner Approximation

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