按年被提到
20242025 · 3 次2026
算法与数据结构›经典算法与数据结构·arXiv:2405.00807 · cs.DS

Nearly Optimal List Labeling

Michael A. Bender, Alex Conway, Martín Farach-Colton, Hanna Komlós, Michal Koucký, William Kuszmaul, Michael Saks · 2024
开始阅读 ↗PDFalphaXiv 讨论
被提及 · 3 人首次 2025-01-25 · 最近 2025-02-19
3不同的人
2活跃月份
2讨论串
2被引(OpenAlex)
arXiv 摘要(候选层不写导读)

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 \operatorname{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.

候选层:至少 2 个不同的人、在 2 个不同月份提到过,还没到主书架的 3 人 3 个月。没有做立场标注,所以只写“被提及”。

HN 书评

推荐在前,同类按时间 · 每篇最多保留 20 条,统计用全部提及
评论teleforce · 2025-01

“Am I the only one that's trying to find the main papers that're being described in the article both the original problem, and the near optimal algorithm paper [1],[2]. Apparently both of them are linked deep inside the article, perhaps Quanta can make it mandatory to list all the reference towards the end of the article, it will be very helpful for the r…”

New book-sorting algorithm almost reaches perfection原评论 ↗
评论svat · 2025-01

“Both papers are linked very clearly in the article, and it was easy to quickly find them just skimming through the article without even reading: > This problem was introduced in a 1981 paper where "1981 paper" links to https://link.springer.com/chapter/10.1007/3-540-10843-2_34 and in the next paragraph: > Last year, in a study that was presented at th…”

New book-sorting algorithm almost reaches perfection原评论 ↗
评论gaudat · 2025-02

“This post links to Quanta [https://www.quantamagazine.org/new-book-sorting-algorithm-almost-reaches-perfection-20250124/], which links to the actual paper [https://arxiv.org/abs/2405.00807]. Tbh I was expecting a supercharged Dewey Decimals...”

This New Algorithm for Sorting Books or Files Is Close to Perfection原评论 ↗