A deamortization approach for dynamic spanner and dynamic maximal matching

Bernstein A, Forster S, Henzinger MH. 2021. A deamortization approach for dynamic spanner and dynamic maximal matching. ACM Transactions on Algorithms. 17(4), 29.

Download (ext.)

Journal Article | Published | English

Scopus indexed
Author
Bernstein, Aaron; Forster, Sebastian; Henzinger, MonikaISTA
Abstract
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.
Publishing Year
Date Published
2021-10-04
Journal Title
ACM Transactions on Algorithms
Acknowledgement
The conference version of this article [10] had an error in the analysis of the dynamic matching algorithm. In particular, Lemma 4.5 assumed an independence between adversarial updates to the hierarchy that is in fact true, but which requires a sophisticated proof. We are very grateful to the anonymous reviewers of Transactions on Algorithms for pointing out this mistake in our analysis. The mistake is fixed in Section 4.5. Almost the entire fix is a matter of analysis: the only change to the algorithm itself is the introduction of responsible bits in Algorithm 2. The first author would like to thank Mikkel Thorup and Alan Roytman for a very helpful discussion of the proof of Theorem 1.1.
Volume
17
Issue
4
Article Number
29
ISSN
eISSN
IST-REx-ID

Cite this

Bernstein A, Forster S, Henzinger MH. A deamortization approach for dynamic spanner and dynamic maximal matching. ACM Transactions on Algorithms. 2021;17(4). doi:10.1145/3469833
Bernstein, A., Forster, S., & Henzinger, M. H. (2021). A deamortization approach for dynamic spanner and dynamic maximal matching. ACM Transactions on Algorithms. Association for Computing Machinery. https://doi.org/10.1145/3469833
Bernstein, Aaron, Sebastian Forster, and Monika H Henzinger. “A Deamortization Approach for Dynamic Spanner and Dynamic Maximal Matching.” ACM Transactions on Algorithms. Association for Computing Machinery, 2021. https://doi.org/10.1145/3469833.
A. Bernstein, S. Forster, and M. H. Henzinger, “A deamortization approach for dynamic spanner and dynamic maximal matching,” ACM Transactions on Algorithms, vol. 17, no. 4. Association for Computing Machinery, 2021.
Bernstein A, Forster S, Henzinger MH. 2021. A deamortization approach for dynamic spanner and dynamic maximal matching. ACM Transactions on Algorithms. 17(4), 29.
Bernstein, Aaron, et al. “A Deamortization Approach for Dynamic Spanner and Dynamic Maximal Matching.” ACM Transactions on Algorithms, vol. 17, no. 4, 29, Association for Computing Machinery, 2021, doi:10.1145/3469833.
All files available under the following license(s):
Copyright Statement:
This Item is protected by copyright and/or related rights. [...]

Link(s) to Main File(s)
Access Level
OA Open Access

Export

Marked Publications

Open Data ISTA Research Explorer

Sources

arXiv 1810.10932

Search this title in

Google Scholar