Time Efficient Implementation for Online $k$-server Problem on Trees
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866911827205554176 |
|---|---|
| author | Khadiev, Kamil Yagafarov, Maxim |
| author_facet | Khadiev, Kamil Yagafarov, Maxim |
| contents | We consider online algorithms for the $k$-server problem on trees of size $n$. Chrobak and Larmore proposed a $k$-competitive algorithm for this problem that has the optimal competitive ratio. However, the existing implementations have $O\left(k^2 + k\cdot \log n\right)$ or $O\left(k(\log n)^2\right)$ time complexity for processing a query, where $n$ is the number of nodes. We propose a new time-efficient implementation of this algorithm that has $O(n)$ time complexity for preprocessing and $O\left(k\log k\right)$ time for processing a query. The new algorithm is faster than both existing algorithms and the time complexity for query processing does not depend on the tree size. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2402_14633 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Time Efficient Implementation for Online $k$-server Problem on Trees Khadiev, Kamil Yagafarov, Maxim Data Structures and Algorithms We consider online algorithms for the $k$-server problem on trees of size $n$. Chrobak and Larmore proposed a $k$-competitive algorithm for this problem that has the optimal competitive ratio. However, the existing implementations have $O\left(k^2 + k\cdot \log n\right)$ or $O\left(k(\log n)^2\right)$ time complexity for processing a query, where $n$ is the number of nodes. We propose a new time-efficient implementation of this algorithm that has $O(n)$ time complexity for preprocessing and $O\left(k\log k\right)$ time for processing a query. The new algorithm is faster than both existing algorithms and the time complexity for query processing does not depend on the tree size. |
| title | Time Efficient Implementation for Online $k$-server Problem on Trees |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2402.14633 |