2025/03/21 by Basiak, Mateusz, Bienkowski, Marcin, Böhm, Martin +4
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2503.17264
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.