- Online Algorithms with Advice: A Survey.
- Joan Boyar, Lene M. Favrholdt, Christian Kudahl, Kim S. Larsen, and Jesper W. Mikkelsen.
ACM SIGACT News, 47(3): 93-129, 2016.
Online algorithms with advice is an area of
research where one attempts to measure how much knowledge
of the future is necessary to achieve a given competitive ratio.
The lower bound results give robust bounds on what is possible using
On the other hand, when the advice is of an obtainable form,
algorithms using advice can lead to semi-online algorithms.
There are strong relationships between advice
complexity and randomization, and advice complexity has led to
the introduction of the first complexity classes for online problems.
This survey concerning online algorithms with advice
explains the models, motivates the study in general,
presents some examples of the work that has been carried out,
and includes a fairly complete set of references, organized
by problem studied.
- Link to the publication at the publisher's site - subscription may be required.
Text required by the publisher (if any):
The publication is available from ACM.
Link to the journal version containing all the material and proofs, some of which are usually omitted in the conference version due to space constraints.
open access (408 KB)
The same as the publisher's version, when the publisher permits. Otherwise, the author's last version before the publisher's copyright; this is often exactly the same, but sometimes fonts, page numbers, figure numbers, etc. are different. It may also be a full version. However, it is safe to read this version, and at the same time cite the official version, as long as references to concrete locations, numbered theorems, etc. inside the article are avoided.
Other publications by the author.