Competitive algorithms for relaxed list update and multilevel caching

We study relaxed list update problem (RLUP), in which access requests are m ade 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 t he 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 h ierarchical memory that consists of a number of caches of increasing size a nd access time. They also proved that a version of LRU is C-competitive, fo r some C, for a restricted class of cost functions. We give an efficient of fline 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 competitiv e ratio of online algorithms for RLUP. (C) 2000 Academic Press.