A Deamortization Approach for Dynamic Spanner and Dynamic Maximal Matching
A Deamortization Approach for Dynamic Spanner and Dynamic Maximal Matching
复制标题
动态 Spanner 和动态最大匹配的去摊方法
DOI：
10.1145/3469833
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
Monika Henzinger
中科院分区：
文献类型：
--
作者：
A. Bernstein;S. Forster;Monika Henzinger
许多动态图算法都有分期更新时间，而不是更强的最坏情况保证。但摊销的数据结构不适合实时系统，因为在实时系统中，每个单独的操作都必须快速执行。出于这个原因，最近有许多随机结果旨在提供比摊销预期更强有力的保证。随机化算法最强有力的保证是它总是正确的(拉斯维加斯)，并且具有高概率的最坏情况更新时间，这给出了高概率保持的每个单独操作的时间界限。在这篇文章中，我们给出了动态扳手和动态最大匹配问题的第一个多对数高概率最坏情况时间界。(1)对于动态扳手，唯一已知的0(N)个最坏情况界是维持3扳手和维持5扳手的高概率最坏情况更新时间O(n3/4)和O(n5/9)。我们给出了维持一个(2k-1)-扳手的高概率最坏时间界为O(1)klog3(N)，它对所有常数k都产生了第一个最坏情况下的PolyLog更新时间。(所有上述结果保持了拉伸2k-1和？(n1+1/k)边的最优折衷。)(2)对于动态最大匹配或动态2-近似最大匹配，没有已知有O(N)个最坏时间界的算法，我们给出了一个高概率最坏时间为O(log5(N))的算法；类似的最坏情况的界只存在于保持匹配是(2+ϵ)-近似的，因此不是最大的。我们的结果是使用一种新的方法来实现的，该方法通过第三种类型的保证将随机数据结构的摊销保证转换为最坏情况的保证，这是上述两者之间的中间基础：如果对于每个更新ɑ，期望处理σ的预期时间至多为σ，则称为算法具有最坏情况的预期更新时间ɑ。尽管比摊销预期更强，但最坏情况下的预期保证并不能解决摊销的基本问题：对于任意高的f(N)，最坏情况下的预期更新时间O(1)仍然允许每1/f(N)次更新需要ϴ(f(N))时间来处理的可能性。在这篇文章中，我们提出了一种黑盒缩减，它将任何具有最坏情况预期更新时间的数据结构转换为具有高概率最坏情况更新时间的数据结构：查询时间保持不变，而更新时间增加了O(log2(N))。因此，我们通过两个步骤来实现我们的结果：(1)首先，我们证明了如何将现有的具有摊销期望多对数运行时间的动态图算法转换为具有最坏情况期望多对数运行时间的算法。(2)然后，我们使用我们的黑盒约简来获得多对数高概率最坏情况的时间界。我们所有的算法都是拉斯维加斯式的算法。
Many dynamic graph algorithms have an amortized update time, rather than a stronger worst-case guarantee. But amortized data structures are not suitable for real-time systems, where each individual operation has to be executed quickly. For this reason, there exist many recent randomized results that aim to provide a guarantee stronger than amortized expected. The strongest possible guarantee for a randomized algorithm is that it is always correct (Las Vegas) and has high-probability worst-case update time, which gives a bound on the time for each individual operation that holds with high probability. In this article, we present the first polylogarithmic high-probability worst-case time bounds for the dynamic spanner and the dynamic maximal matching problem. (1) For dynamic spanner, the only known o(n) worst-case bounds were O(n3/4) high-probability worst-case update time for maintaining a 3-spanner and O(n5/9) for maintaining a 5-spanner. We give a O(1)k log3 (n) high-probability worst-case time bound for maintaining a (2k-1)-spanner, which yields the first worst-case polylog update time for all constant k. (All the results above maintain the optimal tradeoff of stretch 2k-1 and Õ(n1+1/k) edges.) (2) For dynamic maximal matching, or dynamic 2-approximate maximum matching, no algorithm with o(n) worst-case time bound was known and we present an algorithm with O(log 5 (n)) high-probability worst-case time; similar worst-case bounds existed only for maintaining a matching that was (2+ϵ)-approximate, and hence not maximal. Our results are achieved using a new approach for converting amortized guarantees to worst-case ones for randomized data structures by going through a third type of guarantee, which is a middle ground between the two above: An algorithm is said to have worst-case expected update time ɑ if for every update σ, the expected time to process σ is at most ɑ. Although stronger than amortized expected, the worst-case expected guarantee does not resolve the fundamental problem of amortization: A worst-case expected update time of O(1) still allows for the possibility that every 1/f(n) updates requires ϴ (f(n)) time to process, for arbitrarily high f(n). In this article, we present a black-box reduction that converts any data structure with worst-case expected update time into one with a high-probability worst-case update time: The query time remains the same, while the update time increases by a factor of O(log 2(n)). Thus, we achieve our results in two steps: (1) First, we show how to convert existing dynamic graph algorithms with amortized expected polylogarithmic running times into algorithms with worst-case expected polylogarithmic running times. (2) Then, we use our black-box reduction to achieve the polylogarithmic high-probability worst-case time bound. All our algorithms are Las-Vegas-type algorithms.
具有多对数更新时间的全动态最大独立集
DOI：
10.1109/focs.2019.00032
发表时间：
2019
期刊：
{FOCS} 2019
影响因子：
--
作者：
Behnezhad, Soheil;Derakhshan, Mahsa;Hajiaghayi, MohammadTaghi;Stein, Cliff;Sudan, Madhu
通讯作者：
Sudan, Madhu