## 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 language | English (US) |
---|---|

Title of host publication | Proceedings - 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science, FOCS 2022 |

Publisher | IEEE Computer Society |

Pages | 980-990 |

Number of pages | 11 |

ISBN (Electronic) | 9781665455190 |

DOIs | |

State | Published - 2022 |

Event | 63rd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2022 - Denver, United States Duration: Oct 31 2022 → Nov 3 2022 |

### Publication series

Name | Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS |
---|---|

Volume | 2022-October |

ISSN (Print) | 0272-5428 |

### Conference

Conference | 63rd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2022 |
---|---|

Country/Territory | United States |

City | Denver |

Period | 10/31/22 → 11/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 log^{2}n Barrier'. Together they form a unique fingerprint.