Max-Planck-Institut für Informatik
max planck institut
mpii logo Minerva of the Max Planck Society


The influence of lookahead in competitive on-line algorithms

Albers, Susanne

MPI-I-92-143. September 1992, 56 pages. | Status: available - back from printing | Next --> Entry | Previous <-- Entry

Abstract in LaTeX format:
In the competitive analysis of on-line problems, an on-line algorithm is
presented with a sequence of requests to be served.
The on-line algorithm
must satisfy each request without knowledge of any future requests.
We consider the question of lookahead in on-line problems: What
improvement can be achieved in terms of competitiveness, if the
on-line algorithm sees not only the present request but also some
future requests? We introduce two different models of lookahead and
study the ``classical'' on-line
problems such as paging, caching, the $k$-server problem,
the list update
problem and metrical task systems using these two models.
We prove that in the paging problem and the list update problem,
lookahead can significantly reduce the competitive factors of
on-line algorithms without lookahead. In addition
to lower bounds we present a number of on-line algorithms with
lookahead for these two problems. However, we also show that
in more general
on-line problems such as caching, the $k$-server problem and
metrical task systems
lookahead cannot improve competitive factors of deterministic
on-line algorithms without lookahead.
References to related material:

To download this research report, please select the type of document that fits best your needs.Attachement Size(s):
MPI-I-92-143.pdfMPI-I-92-143.pdf28228 KBytes
Please note: If you don't have a viewer for PostScript on your platform, try to install GhostScript and GhostView
URL to this document:
Hide details for BibTeXBibTeX
  AUTHOR = {Albers, Susanne},
  TITLE = {The influence of lookahead in competitive on-line algorithms},
  TYPE = {Research Report},
  INSTITUTION = {Max-Planck-Institut f{\"u}r Informatik},
  ADDRESS = {Im Stadtwald, D-66123 Saarbr{\"u}cken, Germany},
  NUMBER = {MPI-I-92-143},
  MONTH = {September},
  YEAR = {1992},
  ISSN = {0946-011X},