Document Open Access Logo

Online Algorithms for Weighted Paging with Predictions

Authors Zhihao Jiang, Debmalya Panigrahi, Kevin Sun

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2020.69.pdf
  • Filesize: 0.55 MB
  • 18 pages

Document Identifiers

Author Details

Zhihao Jiang
  • Tsinghua University, Beijing, China
Debmalya Panigrahi
  • Duke University, Durham, NC, USA
Kevin Sun
  • Duke University, Durham, NC, USA

Funding

  • Panigrahi, Debmalya: Supported in part by NSF grants CCF-1535972, CCF-1955703, an NSF CAREER Award CCF-1750140, and the Indo-US Virtual Networked Joint Center on Algorithms under Uncertainty.
  • Sun, Kevin: Supported in part by NSF grants CCF-1535972, CCF-1955703, and an NSF CAREER Award CCF-1750140.

Cite AsGet BibTex

Zhihao Jiang, Debmalya Panigrahi, and Kevin Sun. Online Algorithms for Weighted Paging with Predictions. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 69:1-69:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.ICALP.2020.69

Abstract

In this paper, we initiate the study of the weighted paging problem with predictions. This continues the recent line of work in online algorithms with predictions, particularly that of Lykouris and Vassilvitski (ICML 2018) and Rohatgi (SODA 2020) on unweighted paging with predictions. We show that unlike unweighted paging, neither a fixed lookahead nor knowledge of the next request for every page is sufficient information for an algorithm to overcome existing lower bounds in weighted paging. However, a combination of the two, which we call the strong per request prediction (SPRP) model, suffices to give a 2-competitive algorithm. We also explore the question of gracefully degrading algorithms with increasing prediction error, and give both upper and lower bounds for a set of natural measures of prediction error.

Subject Classification

ACM Subject Classification
  • Theory of computation → Online algorithms
Keywords
  • Online algorithms
  • paging

Metrics

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

Related Versions

References

  1. Susanne Albers. The influence of lookahead in competitive paging algorithms. In European Symposium on Algorithms, pages 1-12. Springer, 1993. Google Scholar
  2. Nikhil Bansal, Niv Buchbinder, and Joseph Seffi Naor. A primal-dual randomized algorithm for weighted paging. Journal of the ACM (JACM), 59(4):19, 2012. Google Scholar
  3. Laszlo A. Belady. A study of replacement algorithms for a virtual-storage computer. IBM Systems journal, 5(2):78-101, 1966. Google Scholar
  4. Marek Chrobak, H Karloof, Tom Payne, and S Vishwnathan. New results on server problems. SIAM Journal on Discrete Mathematics, 4(2):172-181, 1991. Google Scholar
  5. Amos Fiat, Richard M Karp, Michael Luby, Lyle A McGeoch, Daniel D Sleator, and Neal E Young. Competitive paging algorithms. Journal of Algorithms, 12(4):685-699, 1991. Google Scholar
  6. Sreenivas Gollapudi and Debmalya Panigrahi. Online algorithms for rent-or-buy with expert advice. In International Conference on Machine Learning, pages 2319-2327, 2019. Google Scholar
  7. Chen-Yu Hsu, Piotr Indyk, Dina Katabi, and Ali Vakilian. Learning-based frequency estimation algorithms. In International Conference on Learning Representations, 2019. Google Scholar
  8. Silvio Lattanzi, Thomas Lavastida, Benjamin Moseley, and Sergei Vassilvitskii. Online scheduling via learned weights. In Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, SODA 2020, Salt Lake City, UT, USA, January 5-8, 2020, pages 1859-1877, 2020. Google Scholar
  9. Thodoris Lykouris and Sergei Vassilvtiskii. Competitive caching with machine learned advice. In International Conference on Machine Learning, pages 3302-3311, 2018. Google Scholar
  10. Michael Mitzenmacher. A model for learned bloom filters and optimizing by sandwiching. In Advances in Neural Information Processing Systems, pages 464-473, 2018. Google Scholar
  11. Rajeev Motwani and Prabhakar Raghavan. Randomized Algorithms. Cambridge University Press, New York, NY, USA, 1995. Google Scholar
  12. Manish Purohit, Zoya Svitkina, and Ravi Kumar. Improving online algorithms via ml predictions. In Advances in Neural Information Processing Systems, pages 9661-9670, 2018. Google Scholar
  13. Dhruv Rohatgi. Near-optimal bounds for online caching with machine learned advice. In Shuchi Chawla, editor, Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, SODA 2020, Salt Lake City, UT, USA, January 5-8, 2020, pages 1834-1845. SIAM, 2020. Google Scholar
  14. Daniel D Sleator and Robert E Tarjan. Amortized efficiency of list update and paging rules. Communications of the ACM, 28(2):202-208, 1985. Google Scholar
  15. Neal Young. On-line caching as cache size varies. In Proceedings of the Second Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '91, pages 241-250, 1991. Google Scholar
  16. Neal E Young. On-line file caching. Algorithmica, 33(3):371-383, 2002. 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 Imprint Privacy Contact