---
_id: '11663'
abstract:
- lang: eng
  text: "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.\r\n\r\nIn this article, we present the first
    polylogarithmic high-probability worst-case time bounds for the dynamic spanner
    and the dynamic maximal matching problem.\r\n\r\n(1)\r\n\r\nFor 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.)\r\n\r\n(2)\r\n\r\nFor 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.\r\n\r\nOur 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)).\r\n\r\nThus, we achieve our results in two steps:\r\n\r\n(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.\r\n\r\n(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."
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.'
article_number: '29'
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Aaron
  full_name: Bernstein, Aaron
  last_name: Bernstein
- first_name: Sebastian
  full_name: Forster, Sebastian
  last_name: Forster
- first_name: Monika H
  full_name: Henzinger, Monika H
  id: 540c9bbd-f2de-11ec-812d-d04a5be85630
  last_name: Henzinger
  orcid: 0000-0002-5008-6530
citation:
  ama: Bernstein A, Forster S, Henzinger M. A deamortization approach for dynamic
    spanner and dynamic maximal matching. <i>ACM Transactions on Algorithms</i>. 2021;17(4).
    doi:<a href="https://doi.org/10.1145/3469833">10.1145/3469833</a>
  apa: Bernstein, A., Forster, S., &#38; Henzinger, M. (2021). A deamortization approach
    for dynamic spanner and dynamic maximal matching. <i>ACM Transactions on Algorithms</i>.
    Association for Computing Machinery. <a href="https://doi.org/10.1145/3469833">https://doi.org/10.1145/3469833</a>
  chicago: Bernstein, Aaron, Sebastian Forster, and Monika Henzinger. “A Deamortization
    Approach for Dynamic Spanner and Dynamic Maximal Matching.” <i>ACM Transactions
    on Algorithms</i>. Association for Computing Machinery, 2021. <a href="https://doi.org/10.1145/3469833">https://doi.org/10.1145/3469833</a>.
  ieee: A. Bernstein, S. Forster, and M. Henzinger, “A deamortization approach for
    dynamic spanner and dynamic maximal matching,” <i>ACM Transactions on Algorithms</i>,
    vol. 17, no. 4. Association for Computing Machinery, 2021.
  ista: Bernstein A, Forster S, Henzinger M. 2021. A deamortization approach for dynamic
    spanner and dynamic maximal matching. ACM Transactions on Algorithms. 17(4), 29.
  mla: Bernstein, Aaron, et al. “A Deamortization Approach for Dynamic Spanner and
    Dynamic Maximal Matching.” <i>ACM Transactions on Algorithms</i>, vol. 17, no.
    4, 29, Association for Computing Machinery, 2021, doi:<a href="https://doi.org/10.1145/3469833">10.1145/3469833</a>.
  short: A. Bernstein, S. Forster, M. Henzinger, ACM Transactions on Algorithms 17
    (2021).
date_created: 2022-07-27T11:09:06Z
date_published: 2021-10-04T00:00:00Z
date_updated: 2024-11-06T12:05:37Z
day: '04'
doi: 10.1145/3469833
extern: '1'
external_id:
  arxiv:
  - '1810.10932'
intvolume: '        17'
issue: '4'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://arxiv.org/abs/1810.10932
month: '10'
oa: 1
oa_version: Preprint
publication: ACM Transactions on Algorithms
publication_identifier:
  eissn:
  - 1549-6333
  issn:
  - 1549-6325
publication_status: published
publisher: Association for Computing Machinery
quality_controlled: '1'
scopus_import: '1'
status: public
title: A deamortization approach for dynamic spanner and dynamic maximal matching
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 17
year: '2021'
...