On the Influence of Lookahead in Competitive Paging Algorithms

Research output: Contribution to journalArticlepeer-review

49 Scopus citations

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 languageEnglish
Pages (from-to)283-305
Number of pages23
JournalAlgorithmica
Volume18
Issue number3
DOIs
StatePublished - Jul 1997
Externally publishedYes

Keywords

  • Competitive analysis
  • Lookahead
  • On-line algorithms
  • Paging

Fingerprint

Dive into the research topics of 'On the Influence of Lookahead in Competitive Paging Algorithms'. Together they form a unique fingerprint.

Cite this