{"arxiv_id":"2609.28397","title":"Transposition achieves OPT$+O(1)$ in polynomial time for IID list update","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)$.","primary_cat":"cs.DS","cross_cats":["cs.DM"],"submitted_at":"2026-09-23T17:03:25+00:00","latest_version":1,"source":"arxiv","source_label":"arXiv","source_url":null,"has_pdf":true,"has_source":false,"verdict":"CONDITIONAL","confidence":"MODERATE","one_line_summary":"For any IID query distribution and any initial list order, the transposition rule achieves expected query cost at most OPT plus 1250 after only n^29 queries.","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","upvotes":0,"downvotes":0,"pith_score":0.0,"inbound_count":1,"_links":{"html":"https://pith.science/paper/2609.28397","verdict":"/api/v1/verdicts/2609.28397"}}