论文标题
在线k-servers问题的快速算法
A Fast Algorithm for Online k-servers Problem on Trees
论文作者
论文摘要
我们考虑在线算法在树上的$ K $ - 服务器问题。这个问题有$ k $竞争的算法，它是最佳竞争比率。 M. Chrobak和L. Larmore提供了它。同时，现有的实现具有$ o（n）$时间复杂性用于处理查询，而$ o（n）$用于填写，其中$ n $是树中的节点数量。该算法的另一个实现具有$ O（k^2+k \ log n）$用于处理查询的时间复杂性，而$ o（n \ log n）$用于预读。我们提供了算法的新的计时效率实现。它具有用于预处理的$ o（n）$时间复杂性，$ o \ left（k（\ log n）^2 \ right）$用于处理查询。
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.
