Limited bookmark randomized online algorithms for the paging problem

Authors
Bein, WW Fleischer, R Larmore, LL
Citation
Ww. Bein et al., Limited bookmark randomized online algorithms for the paging problem, INF PROCESS, 76(4-6), 2000, pp. 155-162
Citations number
10
Categorie Soggetti
Information Tecnology & Communication Systems
Journal title
INFORMATION PROCESSING LETTERS
ISSN journal
00200190 → ACNP
Volume
76
Issue
4-6
Year of publication
2000
Pages
155 - 162
Database
ISI
SICI code
0020-0190(200012)76:4-6<155:LBROAF>2.0.ZU;2-M
Abstract
An efficient randomized online algorithm for the paging problem for cache s ize 2 is given, which is 3/2-competitive against an oblivious adversary. Th e algorithm keeps track of at most one page in slow memory at any time. A l ower bound of 37/24 approximate to 1.5416 is given for the competitiveness of any trackless online algorithm for the same problem, i.e., an algorithm that keeps track of no page outside the cache. (C) 2000 Elsevier Science B. V. All rights reserved.