A 3.3904-Competitive Online Algorithm for List Update with Uniform Costs
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866908481713340416 |
|---|---|
| author | Basiak, Mateusz Bienkowski, Marcin Böhm, Martin Chrobak, Marek Jeż, Łukasz Sgall, Jiří Tatarczuk, Agnieszka |
| author_facet | Basiak, Mateusz Bienkowski, Marcin Böhm, Martin Chrobak, Marek Jeż, Łukasz Sgall, Jiří Tatarczuk, Agnieszka |
| contents | 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$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2503_17264 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | A 3.3904-Competitive Online Algorithm for List Update with Uniform Costs Basiak, Mateusz Bienkowski, Marcin Böhm, Martin Chrobak, Marek Jeż, Łukasz Sgall, Jiří Tatarczuk, Agnieszka Data Structures and Algorithms 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$. |
| title | A 3.3904-Competitive Online Algorithm for List Update with Uniform Costs |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2503.17264 |