5 maja 2026 10:15
[Seminarium ZOK] Mateusz Basiak: A 3.3904-Competitive Online Algorithm for List Update with Uniform Costs
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.
Joint work with Marcin Bieńkowski, Martin Böhm, Marek Chrobak, Łukasz
Jeż, Jiří Sgall and Agnieszka Tatarczuk.
Paper link: https://drops.dagstuhl.de/storage/00lipics/lipics-vol351-esa2025/LIPIcs.ESA.2025.76/LIPIcs.ESA.2025.76.pdf