4 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…
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…