Nearly Optimal List Labeling
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F24%3A10492987" target="_blank" >RIV/00216208:11320/24:10492987 - isvavai.cz</a>
Result on the web
<a href="https://doi.org/10.1109/FOCS61266.2024.00132" target="_blank" >https://doi.org/10.1109/FOCS61266.2024.00132</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1109/FOCS61266.2024.00132" target="_blank" >10.1109/FOCS61266.2024.00132</a>
Alternative languages
Result language
angličtina
Original language name
Nearly Optimal List Labeling
Original language description
The list-labeling problem captures the basic task of storing a dynamically changing set of up to n elements in sorted order in an array of size m=(1+Θ(1))n . The goal is to support insertions and deletions while moving around elements within the array as little as possible. Until recently, the best known upper bound stood at O(log2n) amortized cost. This bound, which was first established in 1981, was finally improved two years ago, when a randomized O(log3/2n) expected-cost algorithm was discovered. The best randomized lower bound for this problem remains Ω(log n), and closing this gap is considered to be a major open problem in data structures. In this paper, we present the See-Saw Algorithm, a randomized list-labeling solution that achieves a nearly optimal bound of O(log n polyloglogn) amortized expected cost. This bound is achieved despite at least three lower bounds showing that this type of result is impossible for large classes of solutions.
Czech name
—
Czech description
—
Classification
Type
D - Article in proceedings
CEP classification
—
OECD FORD branch
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
Result continuities
Project
<a href="/en/project/GA24-10306S" target="_blank" >GA24-10306S: New challenges in streaming, online, and combinatorial algorithms</a><br>
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)
Others
Publication year
2024
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Article name in the collection
Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
ISBN
979-8-3315-1674-1
ISSN
1523-8288
e-ISSN
2575-8454
Number of pages
22
Pages from-to
2253-2274
Publisher name
IEEE
Place of publication
New Jersey, USA
Event location
Chicago, IL, USA
Event date
Oct 27, 2024
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
—