We study relaxed list update problem (RLUP), in which access requests are made to items stored in a list. The cost to access the jth item x(j) is c(j), where c(i) less than or equal to c(i+1) far 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 Aggarwal et at. (1987, "Proc. 19th Symp. Theory of Computing," pp. 305-313) 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. We give an efficient offline algorithm that computes the optimal strategy far RLUP. We: also show an elegant characterization of work functions for RLUP. 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. Finally, we give a lower bound on the competitive ratio of online algorithms for RLUP. (C) 2000 Academic Press. [References: 20]
展开▼
