{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,20]],"date-time":"2026-05-20T16:39:21Z","timestamp":1779295161820,"version":"3.51.4"},"reference-count":18,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2022,10,10]],"date-time":"2022-10-10T00:00:00Z","timestamp":1665360000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"NSF","award":["CCF-1535972, CCF-1955703"],"award-info":[{"award-number":["CCF-1535972, CCF-1955703"]}]},{"name":"NSF CAREER","award":["CCF-1750140"],"award-info":[{"award-number":["CCF-1750140"]}]},{"name":"Indo-US Virtual Networked Joint Center on Algorithms under Uncertainty"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2022,10,31]]},"abstract":"<jats:p>In this article, 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 a knowledge of the next request for every page is sufficient information for an algorithm to overcome the existing lower bounds in weighted paging. However, a combination of the two, which we call strong per request prediction (SPRP), 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.<\/jats:p>","DOI":"10.1145\/3548774","type":"journal-article","created":{"date-parts":[[2022,8,12]],"date-time":"2022-08-12T11:28:46Z","timestamp":1660303726000},"page":"1-27","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":10,"title":["Online Algorithms for Weighted Paging with Predictions"],"prefix":"10.1145","volume":"18","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-9682-2476","authenticated-orcid":false,"given":"Zhihao","family":"Jiang","sequence":"first","affiliation":[{"name":"Stanford University, CA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1799-6660","authenticated-orcid":false,"given":"Debmalya","family":"Panigrahi","sequence":"additional","affiliation":[{"name":"Duke University, NC, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8672-6790","authenticated-orcid":false,"given":"Kevin","family":"Sun","sequence":"additional","affiliation":[{"name":"Duke University, NC, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2022,10,10]]},"reference":[{"key":"e_1_3_2_2_2","doi-asserted-by":"publisher","DOI":"10.1007\/PL00009158"},{"key":"e_1_3_2_3_2","first-page":"345","volume-title":"Proceedings of the 37th International Conference on Machine Learning, (ICML\u201920), 13\u201318 July 2020, Virtual Event (Proceedings of Machine Learning Research)","volume":"119","author":"Antoniadis Antonios","year":"2020","unstructured":"Antonios Antoniadis, Christian Coester, Marek Eli\u00e1s, Adam Polak, and Bertrand Simon. 2020. Online metric algorithms with untrusted predictions. In Proceedings of the 37th International Conference on Machine Learning, (ICML\u201920), 13\u201318 July 2020, Virtual Event (Proceedings of Machine Learning Research), Vol. 119. PMLR, 345\u2013355. http:\/\/proceedings.mlr.press\/v119\/antoniadis20a.html."},{"key":"e_1_3_2_4_2","doi-asserted-by":"publisher","DOI":"10.1145\/2339123.2339126"},{"key":"e_1_3_2_5_2","doi-asserted-by":"publisher","DOI":"10.1147\/sj.52.0078"},{"key":"e_1_3_2_6_2","doi-asserted-by":"publisher","DOI":"10.1137\/0404017"},{"key":"e_1_3_2_7_2","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(91)90041-V"},{"key":"e_1_3_2_8_2","series-title":"Proceedings of the 36th International Conference on Machine Learning (ICML\u201919),","first-page":"2319","volume":"97","author":"Gollapudi Sreenivas","year":"2019","unstructured":"Sreenivas Gollapudi and Debmalya Panigrahi. 2019. Online algorithms for rent-or-buy with expert advice. In Proceedings of the 36th International Conference on Machine Learning (ICML\u201919), 9\u201315 June 2019, Long Beach, California, (Proceedings of Machine Learning Research), Kamalika Chaudhuri and Ruslan Salakhutdinov (Eds.), Vol. 97. PMLR, 2319\u20132327. http:\/\/proceedings.mlr.press\/v97\/gollapudi19a.html."},{"key":"e_1_3_2_9_2","volume-title":"7th International Conference on Learning Representations (ICLR\u201919), (New Orleans, LA, May 6\u20139, 2019)","author":"Hsu Chen-Yu","year":"2019","unstructured":"Chen-Yu Hsu, Piotr Indyk, Dina Katabi, and Ali Vakilian. 2019. Learning-Based frequency estimation algorithms. In 7th International Conference on Learning Representations (ICLR\u201919), (New Orleans, LA, May 6\u20139, 2019). OpenReview.net. https:\/\/openreview.net\/forum?id=r1lohoCqY7."},{"key":"e_1_3_2_10_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975994.114"},{"key":"e_1_3_2_11_2","doi-asserted-by":"publisher","DOI":"10.1145\/3447579"},{"key":"e_1_3_2_12_2","first-page":"462","volume-title":"Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018 (NeurIPS\u201918), (December 3\u20138, 2018, Montr\u00e9al, Canada","author":"Mitzenmacher Michael","year":"2018","unstructured":"Michael Mitzenmacher. 2018. A model for learned bloom filters and optimizing by sandwiching. In Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018 (NeurIPS\u201918), (December 3\u20138, 2018, Montr\u00e9al, Canada), Samy Bengio, Hanna M. Wallach, Hugo Larochelle, Kristen Grauman, Nicol\u00f2 Cesa-Bianchi, and Roman Garnett (Eds.). 462\u2013471. https:\/\/proceedings.neurips.cc\/paper\/2018\/hash\/0f49c89d1e7298bb9930789c8ed59d48-Abstract.html."},{"key":"e_1_3_2_13_2","doi-asserted-by":"publisher","DOI":"10.5555\/211390"},{"key":"e_1_3_2_14_2","first-page":"9684","volume-title":"Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018 (NeurIPS 2018), (December 3\u20138, 2018, Montr\u00e9al, Canada","author":"Purohit Manish","year":"2018","unstructured":"Manish Purohit, Zoya Svitkina, and Ravi Kumar. 2018. Improving online algorithms via ML predictions. In Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018 (NeurIPS 2018), (December 3\u20138, 2018, Montr\u00e9al, Canada), Samy Bengio, Hanna M. Wallach, Hugo Larochelle, Kristen Grauman, Nicol\u00f2 Cesa-Bianchi, and Roman Garnett (Eds.). 9684\u20139693. https:\/\/proceedings.neurips.cc\/paper\/2018\/hash\/73a427badebe0e32caa2e1fc7530b7f3-Abstract.html."},{"key":"e_1_3_2_15_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975994.112"},{"key":"e_1_3_2_16_2","doi-asserted-by":"publisher","DOI":"10.1145\/2786.2793"},{"key":"e_1_3_2_17_2","volume-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX\/RANDOM\u201920)","author":"Wei Alexander","year":"2020","unstructured":"Alexander Wei. 2020. Better and simpler learning-augmented online caching. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX\/RANDOM\u201920). Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik."},{"key":"e_1_3_2_18_2","first-page":"241","volume-title":"Proceedings of the 2nd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201991)","author":"Young Neal","year":"1991","unstructured":"Neal Young. 1991. On-line caching as cache size varies. In Proceedings of the 2nd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201991). 241\u2013250."},{"key":"e_1_3_2_19_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-001-0124-5"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3548774","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3548774","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3548774","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T17:50:53Z","timestamp":1750182653000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3548774"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,10,10]]},"references-count":18,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2022,10,31]]}},"alternative-id":["10.1145\/3548774"],"URL":"https:\/\/doi.org\/10.1145\/3548774","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,10,10]]},"assertion":[{"value":"2020-07-05","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-07-07","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-10-10","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}