46 citations · 313 across the 68 of their papers we have counts for
85 papers
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…
New Structures and Algorithms for Length-Constrained Expander Decompositions
Bernhard Haeupler, D Ellis Hershkowitz, Zihan Tan
Expander decompositions form the basis of one of the most flexible paradigms for close-to-linear-time graph algorithms. Length-constrained expander decompositions generalize this p…
Polylog-Competitive Deterministic Local Routing and Scheduling
Bernhard Haeupler, Shyamal Patel, Antti Roeyskoe +2
This paper addresses point-to-point packet routing in undirected networks, which is the most important communication primitive in most networks. The main result proves the existenc…
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…
Fully Dynamic Consistent -Center Clustering
Jakub Łącki, Bernhard Haeupler, Christoph Grunau +2
We study the consistent k-center clustering problem. In this problem, the goal is to maintain a constant factor approximate -center solution during a sequence of point inser…