We consider online algorithms for the $k$-server problem on trees. There is a $k$-competitive algorithm for this problem, and it is the best competitive ratio. M. Chrobak and L. Larmore provided it. At the same time, the existing implementation has $O(n)$ time complexity for processing a query and $O(n)$ for prepossessing, where $n$ is the number of nodes in a tree. Another implementation of the algorithm has $O(k^2+k\log n)$ time complexity for processing a query and $O(n\log n)$ for prepossessing. We provide a new time-efficient implementation of the algorithm. It has $O(n)$ time complexity for preprocessing and $O\left(k(\log n)^2\right)$ for processing a query.
翻译:我们考虑的是用于树木上的 $k$- server 问题的在线算法。 这个问题有1美元竞争性算法,这是最佳的竞争比率。 M. Chrobak 和 L. Larmore 提供了。 同时, 现有的实施程序有处理查询的O(n) 美元时间复杂性, 预留的O(n) 美元(n) 美元(n) 时间复杂性, 其中一棵树上的节点数为 $(n) 。 另一种实施程序有处理查询的O(k) 2+k\log n) 时间复杂性, 预存的O(n) 美元(n) 时间复杂性。 我们提供了新的具有时间效率的算法实施。 预处理前的算法有 $(n) 美元(n) 时间复杂性, 处理查询的$O\left(k n)\\\\\\\\\\ right) 。