Time Efficient Implementation for Online K-Server Problem on Trees

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.