2026-10-09T20:53:09Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:24544 2025-12-16T13:00:37Z ddc:004 open_access

A 3.3904-Competitive Online Algorithm for List Update with Uniform Costs Basiak, Mateusz Bienkowski, Marcin Böhm, Martin Chrobak, Marek Jeż, Łukasz Sgall, Jiří Tatarczuk, Agnieszka List update work functions amortized analysis online algorithms competitive analysis 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, improving over the previous best known bound of 4. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Mateusz Basiak and Marcin Bienkowski and Martin Böhm and Marek Chrobak and Łukasz Jeż and Jiří Sgall and Agnieszka Tatarczuk 2025 Is Part Of LIPIcs, Volume 351, 33rd Annual European Symposium on Algorithms (ESA 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2025.76 urn:nbn:de:0030-drops-245442 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2025.76 eng https://creativecommons.org/licenses/by/4.0/legalcode