Online Algorithms with Advice: A Survey

Joan Boyar, Lene Monrad Favrholdt, Christian Kudahl, Kim Skak Larsen, Jesper With Mikkelsen

Publikation: Bidrag til tidsskriftTidsskriftartikelForskningpeer review

Abstrakt

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 an extensive set of references, organized by problem studied.
OriginalsprogEngelsk
Artikelnummer19
TidsskriftACM Computing Surveys
Vol/bind50
Udgave nummer2
Antal sider34
ISSN0360-0300
DOI
StatusUdgivet - 2017

Emneord

  • online algorithms
  • advice complexity
  • competitive analysis
  • approximation

Fingeraftryk Dyk ned i forskningsemnerne om 'Online Algorithms with Advice: A Survey'. Sammen danner de et unikt fingeraftryk.

Citationsformater