A 3.3904-Competitive Online Algorithm for List Update with Uniform Costs
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F25%3A10512218" target="_blank" >RIV/00216208:11320/25:10512218 - isvavai.cz</a>
Result on the web
<a href="https://doi.org/10.4230/LIPIcs.ESA.2025.76" target="_blank" >https://doi.org/10.4230/LIPIcs.ESA.2025.76</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.4230/LIPIcs.ESA.2025.76" target="_blank" >10.4230/LIPIcs.ESA.2025.76</a>
Alternative languages
Result language
angličtina
Original language name
A 3.3904-Competitive Online Algorithm for List Update with Uniform Costs
Original language description
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.
Czech name
—
Czech description
—
Classification
Type
D - Article in proceedings
CEP classification
—
OECD FORD branch
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
Result continuities
Project
<a href="/en/project/GA24-10306S" target="_blank" >GA24-10306S: New challenges in streaming, online, and combinatorial algorithms</a><br>
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)
Others
Publication year
2025
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Article name in the collection
Leibniz International Proceedings in Informatics, LIPIcs
ISBN
978-3-95977-395-9
ISSN
1868-8969
e-ISSN
1868-8969
Number of pages
15
Pages from-to
—
Publisher name
Schloss Dagstuhl, Leibniz-Zentrum für Informatik
Place of publication
Wadern
Event location
Warsaw
Event date
Sep 15, 2025
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
—