Nearly Optimal List Labeling
arxiv(2024)
摘要
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(log^2 n) amortized
cost. This bound, which was first established in 1981, was finally improved two
years ago, when a randomized O(log^3/2 n) 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
polyloglog n) 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.
更多查看译文
AI 理解论文
溯源树
样例
生成溯源树,研究论文发展脉络
Chat Paper
正在生成论文摘要