de.mpg.escidoc.pubman.appbase.FacesBean
Deutsch
 
Hilfe Wegweiser Impressum Kontakt Einloggen
  DetailsucheBrowse

Datensatz

DATENSATZ AKTIONENEXPORT

Freigegeben

Bericht

The influence of lookahead in competitive on-line algorithms

MPG-Autoren
http://pubman.mpdl.mpg.de/cone/persons/resource/persons43989

Albers,  Susanne
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

Externe Ressourcen
Es sind keine Externen Ressourcen verfügbar
Volltexte (frei zugänglich)

MPI-I-92-143.pdf
(beliebiger Volltext), 28MB

Ergänzendes Material (frei zugänglich)
Es sind keine frei zugänglichen Ergänzenden Materialien verfügbar
Zitation

Albers, S.(1992). The influence of lookahead in competitive on-line algorithms (MPI-I-92-143). Saarbrücken: Max-Planck-Institut für Informatik.


Zitierlink: http://hdl.handle.net/11858/00-001M-0000-0014-B70E-E
Zusammenfassung
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.