8 April 2022: Hanna Komlós
Online list labeling: breaking the barrier
The online list-labeling problem is an algorithmic primitive with a
large literature of upper bounds, lower bounds, and applications. The
goal is to store a dynamically-changing set of items in an array
of slots, while maintaining the invariant that the items appear in
sorted order, and while minimizing the relabeling cost, defined to be
the number of items that are moved per insertion/deletion. For the
linear regime, where , an
upper bound of on the relabeling cost has been known
since 1981. A lower bound of is known for
deterministic algorithms and for so-called smooth algorithms, but the
best general lower bound remains . The central open
question in the field is whether is optimal for all
algorithms.
In this paper, we give a randomized data structure that achieves an
expected relabeling cost of per operation. More
generally, if for , the
expected relabeling cost becomes . Our
solution is history independent, meaning that the state of the data
structure is independent of the order in which items are
inserted/deleted. For history-independent data structures, we also prove
a matching lower bound: for all between
and some sufficiently small positive constant, the optimal expected cost
for history-independent list-labeling solutions is
.