Stationary access cost of Transposition under iid requests
Follow the latest progress by email.
For the Transposition list-update rule under independent identically distributed requests, how close is stationary expected access cost to OPT, the cost of ordering items by decreasing request probability? The target is the uniform bound OPT+1.
Why it matters and what counts as progress
Why it matters: It asks for a sharp additive guarantee for a simple adaptive rule under a fixed stochastic request model.
What counts as progress: Improve the uniform additive gap above OPT, prove its sharpness, or establish tighter distribution-dependent stationary costs.
How the problem developed
- 1985 · Algorithm analysis [1]
Daniel D. Sleator and Robert E. Tarjan Analyzed the Transpose list-update rule under adversarial access sequences, distinguishing it from the competitive Move-to-Front rule.
- 24 Feb 2025 · Partial result [2]
Piotr Indyk, Isabelle Quaye, Ronitt Rubinfeld and Sandeep Silwal Proved that stationary Transposition is within a 1+o(1) factor of optimal for heavy-tailed iid request distributions, resolving Rivest’s conjecture in that regime.
- 10 Mar 2026 · Theorem [3]
Christian Coester Proved that the stationary expected access cost of Transposition is at most OPT+1 for iid requests, where OPT orders items by decreasing request probability.
AI contribution
Transposition is Nearly Optimal for IID List Update
In the IID request model, the stationary expected access cost of Transposition is at most OPT+1, where OPT orders items by decreasing request probability. GPT-5 Pro proposed the central inequality sⱼ≤pⱼ and a coefficient-nonnegativity route; Christian Coester supplied the final proof.
Sources
Website timeline
Publication dates and editorial changes.