Nearly Optimal List Labeling

Kód výsledku v 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>

Výsledek na webu

<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>

Jazyk výsledku

angličtina

Název v původním jazyce

Nearly Optimal List Labeling

Popis výsledku v původním jazyce

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.

Název v anglickém jazyce

Nearly Optimal List Labeling

Popis výsledku anglicky

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.

Druh

D - Stať ve sborníku

CEP obor

—

OECD FORD obor

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Projekt

<a href="/cs/project/GA24-10306S" target="_blank" >GA24-10306S: Nové výzvy proudových, online a kombinatorických algoritmů</a><br>

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění

2024

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název statě ve sborníku

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

ISBN

979-8-3315-1674-1

ISSN

1523-8288

e-ISSN

2575-8454

Počet stran výsledku

22

Strana od-do

2253-2274

Název nakladatele

IEEE

Místo vydání

New Jersey, USA

Místo konání akce

Chicago, IL, USA

Datum konání akce

27. 10. 2024

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

—