← 研踪 PaperTrailarXiv:2603.10244 · v2
Transposition Is Nearly Optimal for IID List Update
首次提交 2026-03-11 05:41
版本更新 2026-11-10 02:01
雷达观测 2026-11-10 15:22
摘要
The list update problem is one of the oldest and simplest problems in online algorithms: A set of items must be maintained in a list while requests to these items arrive over time. Whenever an item is requested, the algorithm pays a cost equal to the position of the item in the list. In the i.i.d. model, where requests are drawn independently from a fixed distribution, the static ordering by decreasing access probabilities $p_1\ge p_2\ge \dots \ge p_n$ achieves the minimal expected access cost $\mathrm{OPT}=\sum_{i=1}^n ip_i$. However, $p$ is typically unknown, and approximating it by tracking access frequencies creates undesirable overheads. A 50-year old conjecture by Rivest states that the Transposition rule (swap the requested item with its predecessor) is optimal among memoryless algorithms. While known to be false in the strict sense, prior research provided asymptotic confirmation of Rivest's conjecture for restricted distributions. We show that for all distributions, Transposition has stationary expected access cost at most $\mathrm{OPT}+1$, confirming Rivest's conjecture up to an unavoidable additive constant, and showing near-optimality even among algorithms with memory. More abstractly, it yields a purely memoryless procedure to approximately sort probabilities via sampling.
作者备注：To appear at SODA'27
观测到的版本
相邻记录可能跳过中间版本；首次发现 v2 及以上也会标为版本更新。
v2 · 2026-11-10 02:01 · 最新观测版本
Transposition Is Nearly Optimal for IID List Update
The list update problem is one of the oldest and simplest problems in online algorithms: A set of items must be maintained in a list while requests to these items arrive over time. Whenever an item is requested, the algorithm pays a cost equal to the position of the item in the list. In the i.i.d. model, where requests are drawn independently from a fixed distribution, the static ordering by decreasing access probabilities $p_1\ge p_2\ge \dots \ge p_n$ achieves the minimal expected access cost $\mathrm{OPT}=\sum_{i=1}^n ip_i$. However, $p$ is typically unknown, and approximating it by tracking access frequencies creates undesirable overheads. A 50-year old conjecture by Rivest states that the Transposition rule (swap the requested item with its predecessor) is optimal among memoryless algorithms. While known to be false in the strict sense, prior research provided asymptotic confirmation of Rivest's conjecture for restricted distributions. We show that for all distributions, Transposition has stationary expected access cost at most $\mathrm{OPT}+1$, confirming Rivest's conjecture up to an unavoidable additive constant, and showing near-optimality even among algorithms with memory. More abstractly, it yields a purely memoryless procedure to approximately sort probabilities via sampling.
查看此版本解读 →查看此版本原文 ↗