×

Competitive algorithms for multilevel caching and relaxed list update. (Extended abstract). (English) Zbl 0936.68003

Proceedings of the 9th annual ACM-SIAM symposium on Discrete algorithms. San Francisco, CA, USA, January 25-27, 1998. Philadelphia, PA: SIAM. 87-96 (1998).
Summary: We study the Relaxed List Update Problem (RLUP), in which access requests are made to items stored in a list. The cost to access the \(j\)th item \(x_j\) is \(c_j\), where \(c_i\leq c_{i+ 1}\) for all \(i\). After the access, \(x_j\) can be repeatedly swapped, at no cost, with any item that precedes it in the list. This problem was introduced by A. Aggarwal, B. Alpern, A. K. Chandra and M. Snir [A model for hierarchical memory, Proc. 19th Symp. of Theory of Computing, 305-313 (1987)] as a model for the management of hierarchical memory that consists of a number of caches of increasing size and access time. They also proved that a version of LRU is \(C\)-competitive, for some \(C\), for a restricted class of cost functions.
(1) We give an efficient offline algorithm that computes the optimal strategy for RLUP. We also show an elegant characterization of work functions for RLUP. (2) We prove that Move-To-Front (MTF) is optimally competitive for RLUP with any cost function. An interesting feature of the proof is that it does not involve any estimates on the competitive ratio. (3) We give a lower bound on the competitive ratio of online algorithms for RLUP.
For the entire collection see [Zbl 0904.00049].

MSC:

68M07 Mathematical problems of computer architecture
68M99 Computer system organization
PDFBibTeX XMLCite