Time Efficient Implementation for Online $k$-server Problem on Trees
| Autor: | Khadiev, Kamil, Yagafarov, Maxim |
|---|---|
| Rok vydání: | 2024 |
| Předmět: | |
| Zdroj: | TAMC 2024, LNCS 14637 |
| Druh dokumentu: | Working Paper |
| Popis: | 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. Comment: TAMC 2024. arXiv admin note: text overlap with arXiv:2008.00270 |
| Databáze: | arXiv |
| Externí odkaz: |
|