8 papers
Heaps and Their Working Sets
Bernhard Haeupler, Richard HladÃk, Václav RozhoÅ +1
We construct a heap with strong beyond-worst-case performance guarantees and explore the analysis of such heaps. First, we unify existing notions of the working-set bound for heaps…
Splay trees are almost dynamically optimal
Petr Chmel, Bernhard Haeupler, Richard HladÃk +5
Sleator and Tarjan [JACM, 1985] conjectured that splay trees are dynamically optimal -- that on every access sequence, they perform within a constant factor of the optimal offline…
Fast and Simple Sorting Using Partial Information
Bernhard Haeupler, Richard HladÃk, John Iacono +3
We consider the problem of sorting items, given the outcomes of pre-existing comparisons. We present a simple and natural deterministic algorithm that runs in $O(m + \log T…
Stronger Directed Low-Diameter Decompositions with Sub-Logarithmic Diameter and Separation
Bernhard Haeupler, Richard HladÃk, Shengzhe Wang +1
This paper significantly strengthens directed low-diameter decompositions in several ways. We define and give the first results for separated low-diameter decompositions in directe…
Bidirectional Dijkstra's Algorithm is Instance-Optimal
Bernhard Haeupler, Richard HladÃk, Vaclav Rozhon +2
Although Dijkstra's algorithm has near-optimal time complexity for the problem of finding a shortest path from a given vertex to a given vertex , in practice other algorithm…
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…