文章基本信息
- 标题：Improved Hardness of Approximation of Diameter in the CONGEST Model
- 本地全文：下载
- 作者：Ofer Grossman ; Seri Khoury ; Ami Paz 等
- 期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
- 电子版ISSN：1868-8969
- 出版年度：2020
- 卷号：179
- 页码：1-16
- DOI：10.4230/LIPIcs.DISC.2020.19
- 出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
- 摘要：We study the problem of approximating the diameter D of an unweighted and undirected n-node graph in the congest model. Through a connection to extremal combinatorics, we show that a (6/11 ε)-approximation requires Ω(n^{1/6}/log n) rounds, a (4/7 ε)-approximation requires Ω(n^{1/4}/log n) rounds, and a (3/5 ε)-approximation requires Ω(n^{1/3}/log n) rounds. These lower bounds are robust in the sense that they hold even against algorithms that are allowed to return an additional small additive error. Prior to our work, only lower bounds for (2/3 ε)-approximation were known [Frischknecht et al. SODA 2012, Abboud et al. DISC 2016]. Furthermore, we prove that distinguishing graphs of diameter 3 from graphs of diameter 5 requires Ω(n/log n) rounds. This stands in sharp contrast to previous work: while there is an algorithm that returns an estimate âOS 2/3D âO< ⤠DÌf ⤠D in OÌf(â^Sn D) rounds [Holzer et al. DISC 2014], our lower bound implies that any algorithm for returning an estimate 2/3D ⤠DÌf ⤠D requires ÌfΩ(n) rounds.
- 关键词：Distributed graph algorithms; Approximation algorithms; Lower bounds
