A competitive analysis of the list update problem with lookahead

Research output: Contribution to journalArticlepeer-review

32 Scopus citations


We consider the question of lookahead in the list update problem: What improvement can be achieved in terms of competitiveness if an on-line algorithm sees not only the present request to be served but also some future requests? We introduce two different models of lookahead and study the list update problem using these models. We develop lower bounds on the competitiveness that can be achieved by deterministic on-line algorithms with lookahead. Furthermore, we present on-line algorithms with lookahead that are competitive against static off-line algorithms.

Original languageEnglish
Pages (from-to)95-109
Number of pages15
JournalTheoretical Computer Science
Issue number1-2
StatePublished - 15 May 1998
Externally publishedYes


  • Competitive analysis
  • Linear lists
  • Lookahead
  • On-line algorithms


Dive into the research topics of 'A competitive analysis of the list update problem with lookahead'. Together they form a unique fingerprint.

Cite this