A 3.3904-Competitive Online Algorithm for List Update with Uniform Costs

Kód výsledku v 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>

Výsledek na webu

<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>

Jazyk výsledku

angličtina

Název v původním jazyce

A 3.3904-Competitive Online Algorithm for List Update with Uniform Costs

Popis výsledku v původním jazyce

We consider the List Update problem where the cost of each swap is assumed to be 1. This is in contrast to the &quot;standard&quot; 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.

Název v anglickém jazyce

A 3.3904-Competitive Online Algorithm for List Update with Uniform Costs

Popis výsledku anglicky

We consider the List Update problem where the cost of each swap is assumed to be 1. This is in contrast to the &quot;standard&quot; 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.

Druh

D - Stať ve sborníku

CEP obor

—

OECD FORD obor

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Projekt

<a href="/cs/project/GA24-10306S" target="_blank" >GA24-10306S: Nové výzvy proudových, online a kombinatorických algoritmů</a><br>

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění

2025

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název statě ve sborníku

Leibniz International Proceedings in Informatics, LIPIcs

ISBN

978-3-95977-395-9

ISSN

1868-8969

e-ISSN

1868-8969

Počet stran výsledku

15

Strana od-do

—

Název nakladatele

Schloss Dagstuhl, Leibniz-Zentrum für Informatik

Místo vydání

Wadern

Místo konání akce

Warsaw

Datum konání akce

15. 9. 2025

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

—