文章基本信息

标题：Distributed Distance Approximation
本地全文：下载
作者：Bertie Ancona ; Keren Censor-Hillel ; Mina Dalirrooyfard 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2021
卷号：184
页码：30:1-30:17
DOI：10.4230/LIPIcs.OPODIS.2020.30
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：Diameter, radius and eccentricities are fundamental graph parameters, which are extensively studied in various computational settings. Typically, computing approximate answers can be much more efficient compared with computing exact solutions. In this paper, we give a near complete characterization of the trade-offs between approximation ratios and round complexity of distributed algorithms for approximating these parameters, with a focus on the weighted and directed variants. Furthermore, we study bi-chromatic variants of these parameters defined on a graph whose vertices are colored either red or blue, and one focuses only on distances for pairs of vertices that are colored differently. Motivated by applications in computational geometry, bi-chromatic diameter, radius and eccentricities have been recently studied in the sequential setting [Backurs et al. STOC'18, Dalirrooyfard et al. ICALP'19]. We provide the first distributed upper and lower bounds for such problems. Our technical contributions include introducing the notion of approximate pseudo-center, which extends the pseudo-centers of [Choudhary and Gold SODA'20], and presenting an efficient distributed algorithm for computing approximate pseudo-centers. On the lower bound side, our constructions introduce the usage of new functions into the framework of reductions from 2-party communication complexity to distributed algorithms.
关键词：Distributed Computing; Distance Computation; Algorithms; Lower Bounds