Online Algorithms with Advice: A Survey
ACM SIGACT News · 31.08.2016 · 47 (3) · 93-129
DOI: 10.1145/2993749.2993766 ↗Kurz gefasst
Fachartikel in der Zeitschrift ACM SIGACT News, online erschienen am 31.08.2016. Verfasst von Joan Boyar und 4 weiteren Autor:innen. Die Arbeit wurde bisher 34-mal zitiert (Crossref) und nennt 105 Literaturangaben.
Abstract (Originalsprache)
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 semi-online algorithms. 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.
Zitieren
APA
Boyar, J., Favrholdt, L. M., Kudahl, C., Larsen, K. S., & Mikkelsen, J. W. (2016). Online Algorithms with Advice: A Survey. ACM SIGACT News, 47(3), 93-129. https://doi.org/10.1145/2993749.2993766
Vancouver
Boyar J, Favrholdt LM, Kudahl C, Larsen KS, Mikkelsen JW. Online Algorithms with Advice: A Survey. ACM SIGACT News. 2016;47(3):93-129. doi:10.1145/2993749.2993766
BibTeX
@article{Boyar2016,
author = {Boyar, Joan and Favrholdt, Lene M. and Kudahl, Christian and Larsen, Kim S. and Mikkelsen, Jesper W.},
title = {Online Algorithms with Advice: A Survey},
journal = {ACM SIGACT News},
year = {2016},
volume = {47},
number = {3},
pages = {93--129},
doi = {10.1145/2993749.2993766}
}
EUVIMED