---
res:
  bibo_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.\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.@eng"
  bibo_authorlist:
  - foaf_Person:
      foaf_givenName: Aaron
      foaf_name: Bernstein, Aaron
      foaf_surname: Bernstein
  - foaf_Person:
      foaf_givenName: Sebastian
      foaf_name: Forster, Sebastian
      foaf_surname: Forster
  - foaf_Person:
      foaf_givenName: Monika H
      foaf_name: Henzinger, Monika H
      foaf_surname: Henzinger
      foaf_workInfoHomepage: http://www.librecat.org/personId=540c9bbd-f2de-11ec-812d-d04a5be85630
    orcid: 0000-0002-5008-6530
  bibo_doi: 10.1145/3469833
  bibo_issue: '4'
  bibo_volume: 17
  dct_date: 2021^xs_gYear
  dct_isPartOf:
  - http://id.crossref.org/issn/1549-6325
  - http://id.crossref.org/issn/1549-6333
  dct_language: eng
  dct_publisher: Association for Computing Machinery@
  dct_title: A deamortization approach for dynamic spanner and dynamic maximal matching@
...