4 papers · 1 filter
Dynamic Construction of the Lovász Local Lemma
Bernhard Haeupler, Slobodan MitroviÄ, Srikkanth Ramachandran +2
This paper proves that a wide class of local search algorithms extend as is to the fully dynamic setting with an adaptive adversary, achieving an amortized number of…
Maintaining Random Assignments under Adversarial Dynamics
Bernhard Haeupler, Anton Paramonov
We study and further develop powerful general-purpose schemes to maintain random assignments under adversarial dynamic changes. The goal is to maintain assignments that are (approx…
Universal Optimality of Dijkstra via Beyond-Worst-Case Heaps
Bernhard Haeupler, Richard HladÃk, Václav RozhoÅ +2
In this paper we prove that Dijkstra's shortest-path algorithm, if implemented with a sufficiently efficient heap, is universally optimal in its running time, and with suitable sma…
A Cut-Matching Game for Constant-Hop Expanders
Bernhard Haeupler, Jonas Huebotter, Mohsen Ghaffari
This paper extends and generalizes the well-known cut-matching game framework and provides a novel cut-strategy that produces constant-hop expanders. Constant-hop expanders are a s…