A competitive online algorithm for the paging problem with "shelf" memory

Cited 0 time in webofscience Cited 0 time in scopus
Hong, Sung-Pil
Issue Date
Springer Verlag
Lecture Notes in Computer Science, Vol. 1627/1999 (1999) 400-408
We consider an extension of the two-level paging problem.
Besides a fast memory (the cache) and a slow memory, we postulate a
third memory, called the \shelf", near the fast memory so that it is more
cost-e cient to store or retrieve a page from the shelf than to retrieve a
page from the slow memory. Unlike the standard two-level paging prob-
lem, the extension is not a special case of the K-server problem as it
is not embedded in a space with a symmetric metric. Our goal is to
establish an upper bound on the competitive ratio of this \three-level"
memory paging problem. We show that unless per page storage costs
more than per page retrieval from the shelf, a simple extension of the
well-known LRU algorithm has competitive ratio of 2k + l + 1, where k
and l are, respectively, the capacities of the cache and the shelf. If, in
addition, k l, then the same algorithm is
k + l + 2-competitive
0302-9743 (print)1611-3349 (online)
Files in This Item:
There are no files associated with this item.
Appears in Collections:
College of Engineering/Engineering Practice School (공과대학/대학원)Dept. of Industrial Engineering (산업공학과)Journal Papers (저널논문_산업공학과)
  • mendeley

Items in S-Space are protected by copyright, with all rights reserved, unless otherwise indicated.