Transposition 对独立同分布列表更新问题近乎最优
Transposition Is Nearly Optimal for IID List Update
Christian Coester
AI 速读 基于摘要
作者证明:在请求独立同分布(i.i.d.)的列表更新问题中,无记忆的 Transposition 规则的平稳期望访问成本不超过最优静态排序成本 OPT 加 1,从而在不可避免的加性常数意义下证实了 Rivest 猜想。
cs.DS
查看原文摘要
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.