Competitive Algorithms for Relaxed List Update and Multilevel Caching

✍ Scribed by Marek Chrobak; John Noga

• Publisher: Elsevier Science
• Year: 2000
• Tongue: English
• Weight: 188 KB
• Volume: 34
• Category: Article
• ISSN: 0196-6774
• DOI: 10.1006/jagm.1999.1061

✦ Synopsis

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 is c , where j j c F c for all i. After the access, x can be repeatedly swapped, at no cost, with i i q1 j

any item that precedes it in the list. This problem was introduced by Aggarwal Ž . et al. 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 for 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.