Abstract
We introduce a new model of lookahead for on-line paging algorithms and study several algorithms using this model. A paging algorithm is on-line with strong lookahead l if it sees the present request and a sequence of future requests that contains l pairwise distinct pages. We show that strong lookahead has practical as well as theoretical importance and improves the competitive factors of on-line paging algorithms. This is the first model of lookahead having such properties. In addition to lower bounds we present a number of deterministic and randomized on-line paging algorithms with strong lookahead which are optimal or nearly optimal.
Original language | English |
---|---|
Pages (from-to) | 283-305 |
Number of pages | 23 |
Journal | Algorithmica |
Volume | 18 |
Issue number | 3 |
DOIs | |
State | Published - Jul 1997 |
Externally published | Yes |
Keywords
- Competitive analysis
- Lookahead
- On-line algorithms
- Paging