2026-07-20T07:34:25Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:4947 2024-03-06T10:35:36Z ddc:004 open_access

Paid Exchanges are Worth the Price López-Ortiz, Alejandro Renault, Marc P. Rosén, Adi list update problem online computation online algorithms competitive analysis lower bounds We consider the list update problem as defined in the seminal work on competitive analysis by Sleator and Tarjan [12]. In this problem, a sequence of requests, consisting of items to access in a linked list, is given. After an item is accessed it can be moved to any position forward in the list at no cost (free exchange), and, at any time, any two adjacent items can be swapped at a cost of 1 (paid exchange). The cost to access an item is its current position in the list. The goal is to dynamically rearrange the list so as to minimize the total cost (accrued from accesses and exchanges) over the request sequence. We show a lower bound of 12/11 on the worst-case ratio between the performance of an (offline) optimal algorithm that can only perform free exchanges and that of an (offline) optimal algorithm that can perform both paid and free exchanges. This answers an outstanding question that has been open since 1996 [10]. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Alejandro López-Ortiz and Marc P. Renault and Adi Rosén 2015 Is Part Of LIPIcs, Volume 30, 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2015.636 urn:nbn:de:0030-drops-49476 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2015.636 eng https://creativecommons.org/licenses/by/3.0/legalcode