An Optimal On-Line Algorithm for K Servers on Trees
Marek Chrobák, Lawrence L. Larmore · SIAM Journal on Computing · 1991
The k-server problem is investigated when the metric space is a tree. For this case an on-line k-competitive algorithm for k-servers is presented. The competitiveness ratio k is optimal. The algorithm is memoryless, in the sense that it does not use any information from the past.