The k-server problem is one of the most important and well-studied problems in the area of on-line computation. Its importance stems from the fact that it models many practical problems like multi-level memory paging encountered in operating systems, weighted caching used in the management of web caches, head motion planning of multi-headed disks, and robot motion planning. In this paper, we investigate its randomized version for which Theta (log k)-competitiveness is conjectured and yet hardly any < k competitive algorithms are known, even for the simplest of metric spaces of O(k) size.
展开▼
