DISTRIBUTED SPANNER APPROXIMATION

作     者：Censor-Hillel, Keren Dory, Michal 

作者机构：Technion Dept Comp Sci IL-3200003 Haifa Israel 

出 版 物：《SIAM JOURNAL ON COMPUTING》 (工业与应用数学会计算杂志)

年 卷 期：2021年第50卷第3期

页      面：1103-1147页

核心收录：

学科分类：07[理学] 070104[理学-应用数学] 0701[理学-数学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：Israel Science Foundation [1696/14] European Union 

主　　题：spanners distributed algorithms approximation algorithms hardness of approximation 

摘      要：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 k = 5 requires Omega(n/root alpha log n) rounds using deterministic algorithms or Omega(n/root alpha log n) 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 [L. Barenboim, M. Elkin, and C. Gavoille, Theoret. Comput. Sci., 751 (2016), pp. 2{23], 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 hardness results for weighted k -spanners and for unweighted undirected k-spanners for k = 4 in the CONGEST model. In addition, we show lower bounds for the minimum weighted 2-spanner problem in the CONGEST and LOCAL models. 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 [G. Kortsarz and D. Peleg, J. Algorithms, 17 (1994), pp. 222{236], and is tight if we restrict ourselves to polynomial local computations. An algorithm with this approximation factor was not previously known for the distributed setting. The number of rounds