A 3.3904-Competitive Online Algorithm for List Update with Uniform Costs
Mateusz Basiak, Marcin Bienkowski, Martin Böhm, Marek Chrobak, Łukasz Jeż, Jiří Sgall, Agnieszka Tatarczuk · 2025
Read A 3.3904-Competitive Online Algorithm for List Update with Uniform Costs by Mateusz Basiak, Marcin Bienkowski, Martin Böhm, Marek Chrobak, Łukasz Jeż, Jiří Sgall, Agnieszka Tatarczuk (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2503-17264.txt.
Introduction
Mateusz Basiak and co-authors improve a classic online list problem in a 2025 paper, writing with six colleagues. The list update problem asks how to reorder a list as requests arrive, when swapping neighbors costs one unit each. Unlike the standard model, no free moves toward the front are allowed here. Their new algorithm, Full-Or-Partial-Move, guarantees a cost within about 3.39 times the best offline plan, beating the past bound of four. The gain is a pure theory result for online algorithms.
Catalog record
| CREATOR | Mateusz Basiak, Marcin Bienkowski, Martin Böhm, Marek Chrobak, Łukasz Jeż, Jiří Sgall, Agnieszka Tatarczuk |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 78 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2503-17264
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
A 3.3904-Competitive Online Algorithm for List Update with Uniform Costs Mateusz Basiak, Marcin Bienkowski, Martin Böhm, Marek Chrobak, Łukasz Jeż, Jiří Sgall, Agnieszka Tatarczuk Abstract We consider the List Update problem where the cost of each swap is assumed to be 1. This is in contrast to the “standard” model, in which an algorithm is allowed to swap the requested item with previous items for free. We construct an online algorithm Full-Or-Partial-Move ( Fpm ), whose competitive ratio is at most 3.3904 3.3904 , improving over the previous best known bound of 4 4 . \crefname assumptionAssumptionAssumptions \crefname factFactFacts University of Wrocław University of Wrocław University of Wrocław University of California, Riverside University of Wrocław Charles University University of Wrocław ccs Theory of computation Online algorithms keywords List update, work functions, amortized analysis, online algorithms, competitive analysis † † runningauthor: M. Basiak, M. Bienkowski, M. Böhm, M. Chrobak, Ł. Jeż, J. Sgall and A. Tatarczuk † † copyright: Mateusz Basiak, Marcin Bienkowski, Martin Böhm, Marek Chrobak, Łukasz Jeż, Jiří Sgall, Agnieszka Tatarczuk † † funding: Suppported by Polish National Science Centre grants 2022/45/B/ST6/00559, 2020/39/B/ST6/01679 and 2022/47/D/ST6/02864, National Science Foundation grant CCF-2153723, and by grant 24-10306S of GA ČR. x This work is licensed under the Creative Commons Attribution (CC BY) License. 1 Introduction The List Update problem. In the online List Update problem [ 3 , 21 , 22 ] , the objective is to maintain a set of items stored in a linear list in response to a sequence of access requests. The cost of accessing a requested item is equal to its distance from the front of the list. After each request, an algorithm is allowed to rearrange the list by performing an arbitrary number of swaps of adjacent items. In the model introduced by Sleator and Tarjan in their seminal 1985 paper on competitive analysis [ 26 ] , an algorithm can repeatedly swap the requested item with its preceding item at no cost. These swaps are called free . All other swaps are called paid and have cost 1 each. As in other problems involving self-organizing data structures [ 7 ] , the goal is to construct an online algorithm, i.e., operating without the knowledge of future requests. The cost of such an algorithm is compared to the cost of the optimal offline algorithm; the ratio of the two costs is called the competitive ratio and is subject to minimization. Sleator and Tarjan proved that the algorithm Move-To-Front ( Mtf ), which after each request moves the requested item to the front of the list, is 2 -competitive [ 26 ] . This ratio is known to be optimal if the number of items is unbounded. Their work was the culmination of previous extensive studies of list updating, including experimental results, probabilistic approaches, and earlier attempts at amortized analysis (see [ 15 ] and the references therein). As shown in subsequent work, Mtf is not unique — there are other strategies that achieve ratio 2 , such as TimeStamp [ 2 ] or algorithms based on work function [ 9 ] . In fact, there are infinitely many algorithms that achieve ratio 2 [ 14 , 22 ] . The uniform cost model. Following [ 25 ] , we will refer to the cost model of [ 26 ] as standard , and we will denote it here by \textsf{LUP}_{\mathrm{S}} . This model has been questioned in the literature for not accurately reflecting true costs in some implementations [ 25 , 24 , 23 , 19 ] , with the concept of free swaps being one of the main concerns. A natural approach to address this concern, considered in some later studies (see, e.g., [ 25 , 7 , 22 , 4 , 13 ] ), is simply to charge cost 1 for any swap. We will call it here the uniform cost model and denote it \textsf{LUP}_{1} . A general lower bound of 3 on the competitive ratio of deterministic algorithms for \textsf{LUP}_{1} was given by Reingold et al. [ 25 ] . Changing the cost of free swaps from 0 to 1 at most doubles the cost of any algorithm, so Mtf is no worse than 4 -competitive for \textsf{LUP}_{1} . Surprisingly, no algorithm is known to beat Mtf , i.e., achieve ratio lower than 4 . 1 1 1 The authors of [ 22 ] claimed an upper bound of 3 for \textsf{LUP}_{1} , but later discovered that their proof was not correct (personal communication with S. Kamali). . Our main result. To address this open problem, we develop an online algorithm Full-Or-Partial-Move ( Fpm ) for \textsf{LUP}_{1} with competitive ratio \textstyle{\frac{1}{8}}\!\cdot\!(23+\sqrt{17})\approx 3.3904 , significantly improving the previous upper bound of 4 . Our algorithm Fpm remains 3.3904 -competitive even for the partial cost function, where the cost of accessing location \ell is \ell-1 , instead of the full cost of \ell used in the original definition of List Update [ 26 ] . Both functions have been used in the literature, depending on context and convenience. For any online algorithm, its partial-cost competitive ratio is at least as large as its full-cost ratio, although the difference typically vanishes when the list size is unbounded. We present our analysis in terms of partial costs. Fpm remains 3.3904 -competitive also in the dynamic scenario of List Update that allows operations of insertions and deletions, as in the original definition in [ 26 ] (see Appendix A ). Technical challenges and new ideas. The question whether ratio 3 can be achieved remains open. We also do not know if there is a simple algorithm with ratio below 4 . We have considered some natural adaptions of Mtf and other algorithms that are 2 -competitive for \textsf{LUP}_{\mathrm{S}} , but for all we were able to show lower bounds higher than 3 for \textsf{LUP}_{1} . As earlier mentioned, Mtf is 4 -competitive for \textsf{LUP}_{1} . It is also easy to show that its ratio is not better than 4 : repeatedly request the last item in the list. Ignoring additive constants, the algorithm pays twice the length of the list at each step, while any algorithm that just keeps the list in a fixed order, pays only half the length on the average. The intuition why Mtf performs poorly is that it moves the requested items to front “too quickly”. For the aforementioned adversarial strategy against Mtf , ratio 3 can be obtained by moving the items to front only every other time they are requested. This algorithm, called Dbit , a deterministic variant of algorithm Bit from [ 25 ] and a special case of algorithm Counter in [ 25 ] ; it has been also considered in [ 22 ] . In Appendix B , we show that Dbit is not better than 4 -competitive in the partial cost model, and no better than 3.302 -competitive in the full cost model. One can generalize these approaches by considering a more general class of algorithms that either leave the requested item at its current location or move it to the front. In Appendix B , we show that such a strategy cannot achieve ratio better than