3 papers
cs.DS2026
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…
cs.DS2026
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…
cs.DS2025
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…