Online List Labeling: Breaking the log2n Barrier

Michael A. Bender, Alex Conway, Martin Farach-Colton, Hanna Komlos, William Kuszmaul, Nicole Wein

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    Abstract

    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+T(1))n, an upper bound of O(log2 n) on the relabeling cost has been known since 1981. A lower bound of O(log2n) is known for deterministic algorithms and for so-called smooth algorithms, but the best general lower bound remains O(log n). The central open question in the field is whether O(log2 n) is optimal for all algorithms. In this paper, we give a randomized data structure that achieves an expected relabeling cost of O(log3/2n) per operation. More generally, if m=(1+?)n for ?=O(1), the expected relabeling cost becomes O(?-1 log3/2n). 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/n1/3 and some sufficiently small positive constant, the optimal expected cost for history-independent list-labeling solutions is T(?-1 log3/2n).

    Original languageEnglish (US)
    Title of host publicationProceedings - 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science, FOCS 2022
    PublisherIEEE Computer Society
    Pages980-990
    Number of pages11
    ISBN (Electronic)9781665455190
    DOIs
    StatePublished - 2022
    Event63rd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2022 - Denver, United States
    Duration: Oct 31 2022Nov 3 2022

    Publication series

    NameProceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
    Volume2022-October
    ISSN (Print)0272-5428

    Conference

    Conference63rd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2022
    Country/TerritoryUnited States
    CityDenver
    Period10/31/2211/3/22

    Keywords

    • algorithms
    • data structures
    • history independence
    • order maintenance
    • packed memory array
    • randomized algorithms

    ASJC Scopus subject areas

    • General Computer Science

    Fingerprint

    Dive into the research topics of 'Online List Labeling: Breaking the log2n Barrier'. Together they form a unique fingerprint.

    Cite this