A competitive analysis of the list update problem with lookahead

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

5 Scopus citations

Abstract

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. In addition to lower bounds we present a number of competitive on-line algorithms with lookahead.

Original languageEnglish
Title of host publicationMathematical Foundations of Computer Science 1994 - 19th International Symposium, MFCS 1994, Proceedings
EditorsIgor Privara, Branislav Rovan, Peter Ruzicka
PublisherSpringer Verlag
Pages201-210
Number of pages10
ISBN (Print)9783540583387
DOIs
StatePublished - 1994
Externally publishedYes
Event19th International Symposium on Mathematical Foundations of Computer Science, MFCS 1994 - Kosice, Slovakia
Duration: 22 Aug 199426 Aug 1994

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume841 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference19th International Symposium on Mathematical Foundations of Computer Science, MFCS 1994
Country/TerritorySlovakia
CityKosice
Period22/08/9426/08/94

Fingerprint

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

Cite this