“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…”
Nearly Optimal List Labeling
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 条,统计用全部提及“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…”
“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...”