ONLINE LIST LABELING: BREAKING THE log² n 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 n items in an array of m 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 m = (1 + Θ(1))n, an upper bound of O(log² n) on the relabeling cost has been known since 1981. A lower bound of Ω(log² n) is known for deterministic algorithms and for so-called smooth algorithms, but the best general lower bound remains Ω(log n). The central open question in the field is whether O(log² n) is optimal for all algorithms. In this paper, we give a randomized data structure that achieves an expected relabeling cost of O(log³/² n) per operation. More generally, if m = (1+∊)n for ∊ = O(1), the expected relabeling cost becomes O(∊^-1 log³/² n). 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 1/n¹/³ and some sufficiently small positive constant, the optimal expected cost for history-independent list-labeling solutions is Θ(∊^-1 log³/² n).