TY - GEN
T1 - Online List Labeling
T2 - 63rd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2022
AU - Bender, Michael A.
AU - Conway, Alex
AU - Farach-Colton, Martin
AU - Komlos, Hanna
AU - Kuszmaul, William
AU - Wein, Nicole
N1 - Publisher Copyright:
© 2022 IEEE.
PY - 2022
Y1 - 2022
N2 - 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).
AB - 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).
KW - algorithms
KW - data structures
KW - history independence
KW - order maintenance
KW - packed memory array
KW - randomized algorithms
UR - http://www.scopus.com/inward/record.url?scp=85146341126&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85146341126&partnerID=8YFLogxK
U2 - 10.1109/FOCS54457.2022.00096
DO - 10.1109/FOCS54457.2022.00096
M3 - Conference contribution
AN - SCOPUS:85146341126
T3 - Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
SP - 980
EP - 990
BT - Proceedings - 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science, FOCS 2022
PB - IEEE Computer Society
Y2 - 31 October 2022 through 3 November 2022
ER -