A competitive online algorithm for the paging problem with shelf memory

摘要: We consider an extension of the two-level paging problem. Besides a fast memory (the cache) and slow memory, we postulate third called "shelf", near so that it is more cost-efficient to store or retrieve page from shelf than memory. Unlike standard problem, not special case K-server problem as embedded in space with symmetric metric. Our goal establish upper bound on competitive ratio this "three-level" show unless per storage costs retrieval shelf, simple well-known LRU algorithm has 2k + l 1, where k are, respectively, capacities cache shelf. If, addition, ≤ l, then same 2-competitive.