论文标题
有效且简单的算法，用于耐受的跨跨度
Efficient and Simple Algorithms for Fault Tolerant Spanners
论文作者
论文摘要
最近显示，贪婪算法的一种版本给出了尺寸最佳的易耐故障跨度的结构，至少对于顶点故障。但是，构造该扳手的算法不是多项式时间，最著名的多项式时间算法显着次优。在有关易耐受耐受性的两篇文章的两篇最新论文中，将设计多项式时间算法设计以构建（接近）最佳的耐故障跨度（近 - 最佳故障耐受）的跨度（[[Bodwin，Dinitz，Parter，Vassilevka Williams Soda '18]和[Bodwin，Patel，Patel，Patel Podc '19]）。我们给出了一种令人惊讶的简单算法，该算法在多项式时间内运行，并构建容忍故障的跨度，该跨度非常接近最佳（仅在拉伸中仅通过线性因素），通过修改贪婪的算法以在多项式时间内运行。为了补充这一结果，我们还提供了本地和交货模型中简单的分布式结构。
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.
