- Online Algorithms with Advice: A Survey.
- Joan Boyar, Lene M. Favrholdt, Christian Kudahl, Kim S. Larsen, and Jesper W. Mikkelsen.
ACM Computing Surveys. Accepted for Publication.
In online scenarios requests arrive over time, and each request must
be serviced in an irrevocable manner before the next request arrives.
Online algorithms with advice is an area of research where one
attempts to measure how much knowledge of future requests is necessary
to achieve a given performance level, as defined by the competitive
ratio. When this knowledge, the advice, is obtainable, this leads to
practical algorithms, called semi-online algorithms. On the other
hand, each negative result gives robust results about the limitations
of a broad range of semi-online algorithms. This survey explains the
models for online algorithms with advice, motivates the study in
general, presents some examples of the work that has been carried out,
and includes a quite complete set of references, organized by problem
Other publications by the author.