Transposition achieves OPT+O(1) in polynomial time for IID list update

Clayton Mizgerd

In the authors' words

In the classical list update problem, a set of items must be stored in a list-type structure, where accessing the $i$ -th element costs $i$ . Items will be queried in an IID manner according to some probability distribution $p$ on the items. We want to minimize the expected cost of each query. The optimal order is to place the items in decreasing order of probability $p_{1} \geq p_{2} \geq \dots$ with expected cost $OPT = \sum_{j} j p_{j}$ , but the probability vector $p$ is generally unknown. Thus we use a self-organizing list following the transposition rule: an item is transposed 1 position forward whenever it is queried. Coester (2026) proved that, at stationarity measure for the transposition rule, the expected cost of a query is at most $OPT + 1$ . However, this Markov chain may have arbitrarily slow mixing time. We prove that, for arbitrary $p$ and arbitrary initial orderings $σ$ , after polynomially many queries in the number of items, the expected cost of a query is at most $OPT + O (1)$ .

Main resultThe abstract does not state a limitation.

Transposition achieves OPT+O(1) in polynomial time for IID list update

In the authors' words

More on Algorithms & complexity that day

Fast Geometric Spanners via Approximate Nearest Neighbor Search

Locally Sparsified, Globally Near-Optimal: Matching under Independent Vertex Arrivals

Pacing Equilibria in Abstract Mechanisms

JEV-Star: Fast, Low-Cost StarCraft II Control with Language-Model Planning

Substantive Agency and Computational Non-Anticipability: An Axiomatic Route to a Conditional Separation of P and N P

Transposition achieves OPT $+ O (1)$ in polynomial time for IID list update