neal young / Chrobak22Online

  • It is natural to generalize the k-Server problem by allowing each request to specify not only a point p, but also a subset S of servers that may serve it. To attack this generalization, we focus on uniform and star metrics. For uniform metrics, the problem is equivalent to a generalization of Paging in which each request specifies not only a page p, but also a subset S of cache slots, and is satisfied by having a copy of p in some slot in S. We call this problem Slot-Heterogeneous Paging. We parameterize the problem by specifying an arbitrary family F, and restricting the sets S to F. If all request sets are allowed, the optimal deterministic and randomized competitive ratios are exponentially worse than for standard Paging. As a function of |F| and the cache size k, the optimal deterministic ratio is polynomial. For any laminar family F of height h, the optimal ratios are O(hk) (deterministic) and O(h^2 log k) (randomized). The special case that we call All-or-One Paging extends standard Paging by allowing each request to specify a specific slot to put the requested page in. For All-or-One Paging the optimal competitive ratios are Theta(k) (deterministic) and Theta(log k) (randomized), while the offline problem is NP-hard. We extend the deterministic upper bound to the weighted variant of All-Or-One Paging (a generalization of standard Weighted Paging), showing that it is also Theta(k).

© Copyrights are reserved by the publishers.
Download for personal and limited academic use only.