Decremental all-pairs shortest paths in deterministic near-linear time
Decremental all-pairs shortest paths in deterministic near-linear time
复制标题
确定性近线性时间内的递减全对最短路径
DOI：
10.1145/3406325.3451025
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Chuzhoy, Julia
中科院分区：
文献类型：
--
作者：
Chuzhoy, Julia
研究了无向边权图中的递减全对最短路问题。该问题的输入是一个无向的无顶点边图G，其边的长度为非负，该图经历了一个在线的边删除序列。目标是支持近似最短路径查询：给定G的顶点对x，y，返回一条路径Pconnectingxtoy，其长度在最短x-ypath长度的因子α内，在时间上是（|E（P）|），其中α是算法的近似因子。APSP是最基本和最广泛研究的动态图问题之一。一长串的工作最终在算法中达到了接近最优的保证：对于任何常数0<k ≤ 1和参数k ≥ 1，该算法实现了近似因子（2+ k）k−1，总更新时间O（mn 1/k+o（1）log（nL）），其中L是最长与最短边长度之比。不幸的是，与许多先前的工作一样，该算法是随机的，需要假设一个不经意的对手;也就是说，输入的边缘删除序列是预先固定的，可能不依赖于算法的行为。在许多现实世界的情况下，并在应用程序的APSP静态图问题，这是至关重要的，该算法的作品对自适应对手，边删除序列可能取决于算法的过去的行为任意;理想情况下，这样的算法应该是确定性的。不幸的是，与遗忘对手设置不同，它的适应对手对应物仍然知之甚少。对于未赋权图，[Henzinger，Krinninger and Nanongkai，FOCS '13，SICOMP '16]的算法实现了总更新时间为n（mn/mn）的（1+ n）-近似;[Chuzhoy，Saranurak，SODA'21]的最新确定性算法实现了n2.5 +O（mn）的最佳当前总更新时间保证，具有2 O（1/mn）-乘法和2 O（log 3/4 n/mn）-加法近似。据我们所知，对于任意非负的边权重，最快的当前自适应更新算法的总更新时间为O（n3 logL/n），实现了（1+ n）-近似。即使我们愿意满足于任何o（n）-近似因子，当前已知的算法在加权图中的总更新时间也没有优于Θ（n3），并且在未加权图中的总更新时间也没有优于Θ（n2.5）。几个条件下界表明，没有一个算法具有足够小的近似因子可以实现ano（n3）的总更新时间。我们的主要结果是无向边权图的递减APSP的一个确定性算法，即对任意Ω（1/loglogm）≤ n < 1，逼近因子（logm）2 O（1/n），总更新时间O（m1+O（n）·（logm）O（1/n 2）· logL）.特别地，我们得到了对任何常数f（m）的时间上的（polylogm）-逼近，并且，对于任何缓慢增长的函数f（m），我们得到了时间上的（logm）f（m）-逼近。我们还提供了一个算法，类似的保证递减稀疏邻域覆盖。
We study the decremental All-Pairs Shortest Paths (APSP) problem in undirected edge-weighted graphs. The input to the problem is an undirectedn-vertexm-edge graphGwith non-negative lengths on edges, that undergoes an online sequence of edge deletions. The goal is to support approximate shortest-paths queries: given a pairx,yof vertices ofG, return a pathPconnectingxtoy, whose length is within factor α of the length of the shortestx-ypath, in time Õ(|E(P)|), where α is the approximation factor of the algorithm. APSP is one of the most basic and extensively studied dynamic graph problems.A long line of work culminated in the algorithm of [Chechik, FOCS 2018] with near optimal guarantees: for any constant 0<є≤ 1 and parameterk≥ 1, the algorithm achieves approximation factor (2+є)k−1, and total update timeO(mn1/k+o(1)log(nL)), whereLis the ratio of longest to shortest edge lengths. Unfortunately, as much of prior work, the algorithm is randomized and needs to assume an oblivious adversary; that is, the input edge-deletion sequence is fixed in advance and may not depend on the algorithm’s behavior. In many real-world scenarios, and in applications of APSP to static graph problems, it is crucial that the algorithm works against an adaptive adversary, where the edge deletion sequence may depend on the algorithm’s past behavior arbitrarily; ideally, such an algorithm should be deterministic. Unfortunately, unlike the oblivious-adversary setting, its adaptive-adversary counterpart is still poorly understood. For unweighted graphs, the algorithm of [Henzinger, Krinninger and Nanongkai, FOCS ’13, SICOMP ’16] achieves a (1+є)-approximation with total update time Õ(mn/є); the best current total update time guarantee ofn2.5+O(є)is achieved by the recent deterministic algorithm of [Chuzhoy, Saranurak, SODA’21], with 2O(1/є)-multiplicative and 2O(log3/4n/є)-additive approximation. To the best of our knowledge, for arbitrary non-negative edge weights, the fastest current adaptive-update algorithm has total update timeO(n3logL/є), achieving a (1+є)-approximation. Even if we are willing to settle for anyo(n)-approximation factor, no currently known algorithm has a better than Θ(n3) total update time in weighted graphs and better than Θ(n2.5) total update time in unweighted graphs. Several conditional lower bounds suggest that no algorithm with a sufficiently small approximation factor can achieve ano(n3) total update time. Our main result is a deterministic algorithm for decremental APSP in undirected edge-weighted graphs, that, for any Ω(1/loglogm)≤ є< 1, achieves approximation factor (logm)2O(1/є), with total update timeO(m1+O(є)· (logm)O(1/є2)· logL). In particular, we obtain a (polylogm)-approximation in time Õ(m1+є) for any constant є, and, for any slowly growing functionf(m), we obtain (logm)f(m)-approximation in timem1+o(1). We also provide an algorithm with similar guarantees for decremental Sparse Neighborhood Covers.
登录
查看更多内容
近乎最优的近似递减所有对最短路径
DOI：
10.1109/focs.2018.00025
发表时间：
2018
期刊：
2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS)
影响因子：
--
作者：
S. Chechik
通讯作者：
S. Chechik
次多项式时间内的动态低拉伸生成树
DOI：
--
发表时间：
2020
期刊：
ACM-SIAM Symposium on Discrete Algorithms
影响因子：
--
作者：
S. Chechik;Tianyi Zhang
通讯作者：
Tianyi Zhang
DOI：
10.1137/090776573
发表时间：
2004
期刊：
45th Annual IEEE Symposium on Foundations of Computer Science
影响因子：
--
作者：
L. Roditty;Uri Zwick
通讯作者：
Uri Zwick
一种新的递减单源最短路径算法及其在顶点容量流和切割问题中的应用
DOI：
10.1145/3313276.3316320
发表时间：
2019
期刊：
Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing
影响因子：
--
作者：
Julia Chuzhoy;S. Khanna
通讯作者：
S. Khanna
确定性递减单源最短路径：超出 o(mn) 界限
DOI：
10.1145/2897518.2897521
发表时间：
2016
期刊：
Proceedings of the forty-eighth annual ACM symposium on Theory of Computing
影响因子：
--
作者：
A. Bernstein;S. Chechik
通讯作者：
S. Chechik