论文标题
与应用的接近最佳的减速跳动
Near-Optimal Decremental Hopsets with Applications
论文作者
论文摘要
Given a weighted undirected graph $G=(V,E,w)$, a hopset $H$ of hopbound $β$ and stretch $(1+ε)$ is a set of edges such that for any pair of nodes $u, v \in V$, there is a path in $G \cup H$ of at most $β$ hops, whose length is within a $(1+ε)$ factor from the distance between $u$ and $v$ in $ g $。 我们展示了使用多组轴心兴奋剂维持跃点的第一个有效的降低算法。我们的算法的更新时间与最著名的静态算法相匹配，与聚类因子有关。所有先前的减去型跳出构建体均具有$ 2^{\ log^{ω（1）} n} $的superpolylogarithmic（但次级多项式）的跳动。 HKN，foc'14;车臣，焦点18]。 通过应用我们的减速构建，我们可以在几个距离问题上改善或接近最佳界限。最重要的是，我们展示了如何减少$（2K-1）（1+ε）$ - 近似全对最短路径（对于任何常数$ k \ geq 2）$，以$ \ tilde {o}（n^{1/k}）$ \ tilde {n^{1/k}）$ amortized更新时间和$ o（k）$ QUERY时间。在恒定查询时间示体中，这比以前已知的减少算法的更新时间（通过多项式因素）改善了（通过多项式因素）。此外，它比[chechik，focs'18]的结果有所改善，该结果的查询时间为$ o（\ log \ log（nw））$，其中$ w $是长宽比，摊销更新时间为$ n^{1/k} \ cdot（\ frac {1}> {1}ε） n}）} $。对于稀疏图，我们的建筑几乎与最著名的静态运行时间 /查询时间折衷相匹配。 我们还获得了近乎最佳的边界，以维持近似多源的最短路径和距离草图，并获得改进的边界，以获得近似单源的最短路径。我们的算法是随机的，我们的边界具有很高的可能性与遗忘对手。
Given a weighted undirected graph $G=(V,E,w)$, a hopset $H$ of hopbound $β$ and stretch $(1+ε)$ is a set of edges such that for any pair of nodes $u, v \in V$, there is a path in $G \cup H$ of at most $β$ hops, whose length is within a $(1+ε)$ factor from the distance between $u$ and $v$ in $G$. We show the first efficient decremental algorithm for maintaining hopsets with a polylogarithmic hopbound. The update time of our algorithm matches the best known static algorithm up to polylogarithmic factors. All the previous decremental hopset constructions had a superpolylogarithmic (but subpolynomial) hopbound of $2^{\log^{Ω(1)} n}$ [Bernstein, FOCS'09; HKN, FOCS'14; Chechik, FOCS'18]. By applying our decremental hopset construction, we get improved or near optimal bounds for several distance problems. Most importantly, we show how to decrementally maintain $(2k-1)(1+ε)$-approximate all-pairs shortest paths (for any constant $k \geq 2)$, in $\tilde{O}(n^{1/k})$ amortized update time and $O(k)$ query time. This improves (by a polynomial factor) over the update-time of the best previously known decremental algorithm in the constant query time regime. Moreover, it improves over the result of [Chechik, FOCS'18] that has a query time of $O(\log \log(nW))$, where $W$ is the aspect ratio, and the amortized update time is $n^{1/k}\cdot(\frac{1}ε)^{\tilde{O}(\sqrt{\log n})}$. For sparse graphs our construction nearly matches the best known static running time / query time tradeoff. We also obtain near-optimal bounds for maintaining approximate multi-source shortest paths and distance sketches, and get improved bounds for approximate single-source shortest paths. Our algorithms are randomized and our bounds hold with high probability against an oblivious adversary.
