Efficient and Simple Algorithms for Fault-Tolerant Spanners
Efficient and Simple Algorithms for Fault-Tolerant Spanners
复制标题
容错 Spanner 的高效且简单的算法
DOI：
10.1145/3382734.3405735
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Robelle, Caleb
中科院分区：
文献类型：
--
作者：
Dinitz, Michael;Robelle, Caleb
最近有研究表明，贪心算法的一个版本给出了容错扳手的构造，它至少对于顶点错误是尺寸最优的。然而，构造这个扳手的算法不是多项式时间的，而最著名的多项式时间算法明显不是最优的。在最近的两篇关于容错扳手的论文（[Bodwin, Dinitz, Parter, Vassilevka Williams SODA '18]和[Bodwin， Patel PODC '19]）中，设计一个多项式时间算法来构造（近）最优容错扳手是一个显式开放问题。我们给出了一个惊人的简单算法，该算法在多项式时间内运行，并通过修改贪婪算法使其在多项式时间内运行，构建了非常接近最优的容错扳手（仅在拉伸中偏离线性因子）。为了补充这个结果，我们还在LOCAL和CONGEST模型中给出了简单的分布式结构。
It was recently shown that a version of the greedy algorithm gives a construction of fault-tolerant spanners that is size-optimal, at least for vertex faults. However, the algorithm to construct this spanner is not polynomial-time, and the best-known polynomial time algorithm is significantly suboptimal. Designing a polynomial-time algorithm to construct (near-)optimal fault-tolerant spanners was given as an explicit open problem in the two most recent papers on fault-tolerant spanners ([Bodwin, Dinitz, Parter, Vassilevka Williams SODA '18] and [Bodwin, Patel PODC '19]). We give a surprisingly simple algorithm which runs in polynomial time and constructs fault-tolerant spanners that are extremely close to optimal (off by only a linear factor in the stretch) by modifying the greedy algorithm to run in polynomial time. To complement this result, we also give simple distributed constructions in both the LOCAL and CONGEST models.
登录
查看更多内容
最佳顶点容错扳手（用于固定拉伸）
DOI：
--
发表时间：
2017
期刊：
ACM-SIAM Symposium on Discrete Algorithms
影响因子：
--
作者：
Gregory Bodwin;M. Dinitz;M. Parter;V. V. Williams
通讯作者：
V. V. Williams
传递闭包扳手
DOI：
--
发表时间：
2008
期刊：
SIAM journal on computing (Print)
影响因子：
--
作者：
Arnab Bhattacharyya;Elena Grigorescu;Kyomin Jung;Sofya Raskhodnikova;David P. Woodruff
通讯作者：
David P. Woodruff
顶点容错 Spanner 的一个简单但最佳的解决方案
DOI：
--
发表时间：
2018
期刊：
ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing
影响因子：
--
作者：
Gregory Bodwin;Shyamal Patel
通讯作者：
Shyamal Patel
DOI：
--
发表时间：
1998
期刊：
Symposium on the Theory of Computing
影响因子：
--
作者：
C. Levcopoulos;G. Narasimhan;M. Smid
通讯作者：
M. Smid
DOI：
10.1145/378580.378581
发表时间：
2001-07
期刊：
--
影响因子：
--
作者：
M. Thorup;Uri Zwick
通讯作者：
M. Thorup;Uri Zwick