An Optimal On-Line Algorithm for K Servers on Trees
- 1 February 1991
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 20 (1) , 144-148
- https://doi.org/10.1137/0220008
Abstract
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.Keywords
This publication has 4 references indexed in Scilit:
- A competitive 2-server algorithmInformation Processing Letters, 1991
- A strongly competitive randomized paging algorithmAlgorithmica, 1991
- Memory versus randomization in on-line algorithmsPublished by Springer Nature ,1989
- Competitive snoopy cachingAlgorithmica, 1988