论文标题
使用应用
Dynamic Maintenance of Low-Stretch Probabilistic Tree Embeddings with Applications
论文作者
论文摘要
我们给出了第一个非平凡的全动态概率树嵌入算法，以进行边缘插入和删除的加权图。我们在摊销的更新时间和预期的对抗对手之间获得了权衡。在此权衡的两个极端情况下，我们可以在更新时间$ m^{1/2 + o（1）} $或预期伸展的$ n^{o（1）} $的树中维护一棵预期的拉伸$ o（\ log^4 n）$，并带有更新时间$ n^{o（1）} $（用于Edge $ n^{o（1）} $（用于$ n $ n $ n $ n $ n $）。到目前为止，后一种类型的保证仅因维持平均（而不是预期的）伸展的树嵌入[Chechik/Zhang，Soda '20]而闻名。 我们的主要结果对完全动态的近似距离甲骨文和完全动态的购买网络设计具有直接影响。对于动态距离甲壳，我们的结果是第一个打破$ O（\ sqrt {M}）$更新时间屏障的结果。对于购买式网络设计，在静态设置中也很大程度上依赖于概率树的嵌入，我们给出了第一个非平凡的动态算法。由于概率树嵌入是静态近似算法中的重要工具，因此可以想象我们在动态近似算法中的进一步应用。 从技术的角度来看，我们首先设计了通过仔细组合Bartal的球增长方法[FOCS '96]与Chechik和Zhang [Soda '20]的修剪框架的仔细组合，从而获得了概率低直径分解的降低算法。然后，我们通过通过新的自举构想丰富了众所周知的“减少到完全动态”的降低，将其扩展到完整的动态算法，以递归采用完全动态的算法，而不是这种降低中的静态算法。
We give the first non-trivial fully dynamic probabilistic tree embedding algorithm for weighted graphs undergoing edge insertions and deletions. We obtain a trade-off between amortized update time and expected stretch against an oblivious adversary. At the two extremes of this trade-off, we can maintain a tree of expected stretch $ O (\log^4 n) $ with update time $ m^{1/2 + o(1)} $ or a tree of expected stretch $ n^{o(1)} $ with update time $ n^{o(1)} $ (for edge weights polynomial in $ n $). A guarantee of the latter type has so far only been known for maintaining tree embeddings with average (instead of expected) stretch [Chechik/Zhang, SODA '20]. Our main result has direct implications to fully dynamic approximate distance oracles and fully dynamic buy-at-bulk network design. For dynamic distance oracles, our result is the first to break the $ O (\sqrt{m}) $ update-time barrier. For buy-at-bulk network design, a problem which also in the static setting heavily relies on probabilistic tree embeddings, we give the first non-trivial dynamic algorithm. As probabilistic tree embeddings are an important tool in static approximation algorithms, further applications of our result in dynamic approximation algorithms are conceivable. From a technical perspective, we obtain our main result by first designing a decremental algorithm for probabilistic low-diameter decompositions via a careful combination of Bartal's ball-growing approach [FOCS '96] with the pruning framework of Chechik and Zhang [SODA '20]. We then extend this to a fully dynamic algorithm by enriching a well-known 'decremental to fully dynamic' reduction with a new bootstrapping idea to recursively employ a fully dynamic algorithm instead of a static one in this reduction.
