46 citations · 313 across the 68 of their papers we have counts for
55 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…
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…
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…
Parallel Greedy Spanners
Bernhard Haeupler, D Ellis Hershkowitz, Zihan Tan
A -spanner of a graph is a subgraph that -approximates pairwise distances. The greedy algorithm is one of the simplest and most well-studied algorithms for constructing a spa…