Document Open Access Logo

Online Algorithms with Predictions (Invited Talk)

Author Joan Boyar

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2023.2.pdf
  • Filesize: 449 kB
  • 2 pages

Document Identifiers

Author Details

Joan Boyar
  • University of Southern Denmark, Odense, Denmark

Funding

Supported in part by the Independent Research Fund Denmark, Natural Sciences, grant DFF-0135-00018B, and in part by the Innovation Fund Denmark, grant 9142-00001B, Digital Research Centre Denmark, project P40: Online Algorithms with Predictions.

Cite As Get BibTex

Joan Boyar. Online Algorithms with Predictions (Invited Talk). In 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 272, pp. 2:1-2:2, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023) https://doi.org/10.4230/LIPIcs.MFCS.2023.2

Abstract

We give an introduction to online algorithms with predictions, from an algorithms researcher’s perspective, concentrating on minimization problems.

Subject Classification

ACM Subject Classification
  • Theory of computation → Online algorithms
Keywords
  • Online algorithms with predictions
  • online algorithms with advice
  • random order analysis

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Algorithms with predictions. https://algorithms-with-predictions.github.io/. Accessed: 2023-07-10.
  2. Antonios Antoniadis, Joan Boyar, Marek Eliás, Lene M. Favrholdt, Ruben Hoeksma, Kim S. Larsen, Adam Polak, and Bertrand Simon. Paging with succinct predictions. CoRR, abs/2210.02775, 2022. To appear in ICML 2023. URL: https://doi.org/10.48550/arXiv.2210.02775.
  3. Magnus Berg, Joan Boyar, Lene M. Favrholdt, and Kim S. Larsen. Online minimum spanning trees with weight predictions. CoRR, abs/2302.12029, 2023. To appear in WADS 2023. URL: https://doi.org/10.48550/arXiv.2302.12029.
  4. Hans-Joachim Böckenhauer, Dennis Komm, Rastislav Královic, Richard Královic, and Tobias Mömke. Online algorithms with advice: The tape model. Information and Computation, 254:59-83, 2017. Google Scholar
  5. Stefan Dobrev, Rastislav Královič, and Dana Pardubská. Measuring the problem-relevant information in input. RAIRO - Theor. Inf. Appl., 43(3):585-613, 2009. Google Scholar
  6. Yuval Emek, Pierre Fraigniaud, Amos Korman, and Adi Rosén. Online computation with advice. Theor. Comput. Sci., 412:2642-2656, 2011. Google Scholar
  7. Juraj Hromkovič, Rastislav Královič, and Richard Královič. Information complexity of online problems. In MFCS, volume 6281 of LNCS, pages 24-36. Springer, 2010. Google Scholar
  8. Claire Kenyon. Best-fit bin-packing with random order. In 7th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 359-364. SIAM, 1996. Google Scholar
  9. Thodoris Lykouris and Sergei Vassilvitskii. Competitive caching with machine learned advice. In Jennifer G. Dy and Andreas Krause, editors, 35th International Conference on Machine Learning (ICML), volume 80 of Proceedings of Machine Learning Research, pages 3302-3311, 2018. Google Scholar
  10. Thodoris Lykouris and Sergei Vassilvitskii. Competitive caching with machine learned advice. Journal of the ACM, 68(4):24:1-24:25, 2021. Google Scholar
  11. Manish Purohit, Zoya Svitkina, and Ravi Kumar. Improving online algorithms via ML predictions. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett, editors, 31st Advances in Neural Information Processing Systems (NeurIPS), volume 31, pages 9684-9693. Curran Associates, Inc., 2018. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact