2020/05/31 by Kamil Khadiev, Khadiev, Kamil, Maxim Yagafarov +1
Computer Science · #Complexity and Algorithms in Graphs #Cryptography and Data Security #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Optimization and Search Problems
paper · pdf · doi:10.48550/arxiv.2006.00605
openalex publication_date 2020/05/31 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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(k2+klog n) time complexity for processing a query and O(nlog n) for prepossessing. We provide a new time-efficient implementation of the algorithm. It has O(n) time complexity for preprocessing and O(k(log n)2) for processing a query.