Skip to content
Preprint

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

Sep 2026 · 0 citations · 10 references
Computer Science

TL;DR

It is proved that, for arbitrary $p and arbitrary initial orderings $\sigma$ and arbitrary initial orderings $\sigma$, after polynomially many queries in the number of items, the expected cost of a query is at most $\mathsf{OPT} + O(1)$.

Abstract

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 \cdots$ with expected cost $\mathsf{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 $\mathsf{OPT} + 1$. However, this Markov chain may have arbitrarily slow mixing time. We prove that, for arbitrary $p$ and arbitrary initial orderings $\sigma$, after polynomially many queries in the number of items, the expected cost of a query is at most $\mathsf{OPT} + O(1)$.

View source

Similar papers

Preprint Sep 2026

Union-Find with Constant-Time Deletions Across the Optimal Worst-Case Tradeoff

We consider union-find with deletions, where the representation and the cost of a query must depend on the current number of live elements rather than on the number of elements ever created. For every integer parameter $k\ge 2$, we give a linear-space data structure supporting $\mathsf{MakeSet}$ in $O(1)$ worst-case ti...

Han-Qing Li, Ze Hong · 0 citations
Preprint Oct 2026

Selection under partial information

The selection problem asks to find the $k$-th smallest element in a given set $X$. Its complexity is well-known to be $\Theta(|X|)$ for every fixed $k$. We consider the poset selection problem where a partial order $P$ on $X$ is given, and the underlying order of $X$ is guaranteed to be a linear extension of $P$. This...

Benjamin Aram Berendsohn · 0 citations
Sep 2026

Quantum Query Complexity for List Search

This paper gives a precise characterization of when the ambient address space yields a genuine quantum advantage for linked-list search, and extends the results and gives the same tight asymptotic bounds for the natural double linked-list version as well.

Niranka Banerjee, Akinori Kawachi · 0 citations
Sep 2026

A 3.1462-Competitive Algorithm for Matroid Secretary

The ordinal algorithm accepts every element of a fixed canonical optimum with probability exactly $1/C_*$ and uses O(n^2)$ independence queries and the resulting guarantee has a direct analytic proof.

Hau Chan, Jia-Nan Lin, Chen-Hao Wang · 5 citations · ⚡2
Sep 2026

Matrix-Vector Complexity of Low-Rank Approximation

The proof extends adaptive Wishart deferred decisions to a rectangular factor with a $k$-dimensional nullspace while persistence of small compression eigenvalues controls growing $p$ and the spectral endpoint.

Hai-Han Zhang, Wen-Dao Wu, Chen-Heng Zhang et al. · 1 citation
Preprint Sep 2026

Online matching games in bipartite expanders: applications to bitprobes and dictionaries with non-adaptive probing

A dictionary is a data structure which stores pairs (key, value). The operation query on input key returns value if the dictionary contains a pair (key, value) and nil otherwise. A dynamic dictionary also supports the insert and delete operations. The model with cells of bitsize $n + m + 1$ is used, where $n$ and $m$ a...

Bruno Bauwens, Marius Zimand · 0 citations

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.