查看文章

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 …