{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,8]],"date-time":"2026-07-08T18:45:23Z","timestamp":1783536323234,"version":"3.55.0"},"publisher-location":"New York, NY, USA","reference-count":38,"publisher":"ACM","license":[{"start":{"date-parts":[[2026,7,6]],"date-time":"2026-07-06T00:00:00Z","timestamp":1783296000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/legalcode"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2026,7,6]]},"DOI":"10.1145\/3816782.3819196","type":"proceedings-article","created":{"date-parts":[[2026,7,8]],"date-time":"2026-07-08T17:28:33Z","timestamp":1783531713000},"page":"380-391","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Tight Latency Guarantees for Weighted Caching with Delayed Hits"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0009-0000-1564-216X","authenticated-orcid":false,"given":"Tomer","family":"Tsachor","sequence":"first","affiliation":[{"name":"Technion, Haifa, Israel"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0009-4234-9466","authenticated-orcid":false,"given":"Joseph (Seffi)","family":"Naor","sequence":"additional","affiliation":[{"name":"Technion, Haifa, Israel"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2026,7,8]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(98)00116-9"},{"key":"e_1_3_2_1_2_1","volume-title":"Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms, 17\u201319","author":"Albers Susanne","year":"1999","unstructured":"Susanne Albers, Sanjeev Arora, and Sanjeev Khanna. Page replacement for general caching problems. In Robert Endre Tarjan and Tandy J. Warnow, editors, Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms, 17\u201319 January 1999, Baltimore, Maryland, USA, pages 31\u201340. ACM\/SIAM, 1999."},{"key":"e_1_3_2_1_3_1","volume-title":"Min-cost bipartite perfect matching with delays. Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX\/RANDOM","author":"Ashlagi Itai","year":"2017","unstructured":"Itai Ashlagi, Yossi Azar, Moses Charikar, Ashish Chiplunkar, Ofir Geri, Haim Kaplan, Rahul Makhijani, Yuyi Wang, and Roger Wattenhofer. Min-cost bipartite perfect matching with delays. Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX\/RANDOM 2017), 81:1, 2017."},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/3387514.3405883"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974782.67"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055475"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-019-09963-7"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2019.00013"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS46700.2020.00129"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1137\/090779000"},{"key":"e_1_3_2_1_11_1","volume-title":"A primal-dual randomized algorithm for weighted paging. Journal of the ACM (JACM), 59(4):19","author":"Bansal Nikhil","year":"2012","unstructured":"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."},{"key":"e_1_3_2_1_12_1","volume-title":"What to do with your free time: algorithms for infrequent requests and randomized weighted caching","author":"Blum A.","year":"1996","unstructured":"A. Blum, M. Furst, and A. Tomkins. What to do with your free time: algorithms for infrequent requests and randomized weighted caching, 1996."},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.5555\/795665.796507"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188798"},{"key":"e_1_3_2_1_15_1","first-page":"444","volume-title":"Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014","author":"Buchbinder Niv","year":"2014","unstructured":"Niv Buchbinder, Shahar Chen, and Joseph Naor. Competitive analysis via regularization. In Chandra Chekuri, editor, Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014, Portland, Oregon, USA, January 5\u20137, 2014, pages 436\u2013444. SIAM, 2014."},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1561\/0400000024"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1137\/0220008"},{"key":"e_1_3_2_1_18_1","first-page":"344","volume-title":"Online matching: haste makes waste! In Proceedings of the forty-eighth annual ACM symposium on Theory of Computing","author":"Emek Yuval","year":"2016","unstructured":"Yuval Emek, Shay Kutten, and Roger Wattenhofer. Online matching: haste makes waste! In Proceedings of the forty-eighth annual ACM symposium on Theory of Computing, pages 333\u2013344, 2016."},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/3210377.3210404"},{"key":"e_1_3_2_1_20_1","volume-title":"Algorithms and Techniques","author":"Fairstein Yaron","year":"2024","unstructured":"Yaron Fairstein, Joseph Seffi Naor, and Tomer Tsachor. Distributional online weighted paging with limited horizon. Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2024."},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(91)90041-V"},{"key":"e_1_3_2_1_22_1","first-page":"66","volume-title":"15th USENIX Symposium on Networked Systems Design and Implementation (NSDI 18)","author":"Firestone Daniel","year":"2018","unstructured":"Daniel Firestone, Andrew Putnam, Sambhrama Mundkur, Derek Chiou, Alireza Dabagh, Mike Andrewartha, Hari Angepat, Vivek Bhanu, Adrian Caulfield, Eric Chung, et al. Azure accelerated networking:{SmartNICs} in the public cloud. In 15th USENIX Symposium on Networked Systems Design and Implementation (NSDI 18), pages 51\u201366, 2018."},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975482.10"},{"key":"e_1_3_2_1_24_1","first-page":"1138","volume-title":"Proccedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020","author":"Gupta Anupam","year":"2020","unstructured":"Anupam Gupta, Amit Kumar, and Debmalya Panigrahi. Caching with time windows. In Konstantin Makarychev, Yury Makarychev, Madhur Tulsiani, Gautam Kamath, and Julia Chuzhoy, editors, Proccedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020, Chicago, IL, USA, June 22\u201326, 2020, pages 1125\u20131138. ACM, 2020."},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/INFOCOM55648.2025.11044511"},{"key":"e_1_3_2_1_26_1","series-title":"Lecture Notes in Computer Science","first-page":"73","volume-title":"Online Algorithms, The State of the Art (the book grow out of a Dagstuhl Seminar","author":"Irani Sandy","year":"1996","unstructured":"Sandy Irani. Competitive analysis of paging. In Amos Fiat and Gerhard J. Woeginger, editors, Online Algorithms, The State of the Art (the book grow out of a Dagstuhl Seminar, June 1996), volume 1442 of Lecture Notes in Computer Science, pages 52\u201373. Springer, 1996."},{"key":"e_1_3_2_1_27_1","first-page":"710","volume-title":"Proceedings of the Twenty-Ninth Annual ACM Symposium on the Theory of Computing","author":"Irani Sandy","year":"1997","unstructured":"Sandy Irani. Page replacement with multi-size pages and applications to web caching. In Frank Thomson Leighton and Peter W. Shor, editors, Proceedings of the Twenty-Ninth Annual ACM Symposium on the Theory of Computing, El Paso, Texas, USA, May 4\u20136, 1997, pages 701\u2013710. ACM, 1997."},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-001-0095-6"},{"key":"e_1_3_2_1_29_1","first-page":"2405","volume-title":"23rd USENIX Symposium on Networked Systems Design and Implementation (NSDI 26)","author":"Keren Nadav","year":"2026","unstructured":"Nadav Keren, Gil Einziger, and Gabriel Scalosub. {Latency-Aware} caching with delayed hits: From bursty traffic to pipeline architectures. In 23rd USENIX Symposium on Networked Systems Design and Implementation (NSDI 26), pages 2389\u20132405, 2026."},{"key":"e_1_3_2_1_30_1","series-title":"Proceedings of Machine Learning Research","first-page":"3311","volume-title":"Jennifer G. Dy and Andreas Krause","author":"Lykouris Thodoris","year":"2018","unstructured":"Thodoris Lykouris and Sergei Vassilvitskii. Competitive caching with machine learned advice. In Jennifer G. Dy and Andreas Krause, editors, Proceedings of the 35th International Conference on Machine Learning, ICML 2018, Stockholmsm\u00e4ssan, Stockholm, Sweden, July 10\u201315, 2018, volume 80 of Proceedings of Machine Learning Research, pages 3302\u20133311. PMLR, 2018."},{"key":"e_1_3_2_1_31_1","volume-title":"Lower bounds for caching with delayed hits. arXiv preprint arXiv:2006.00376","author":"Manohar Peter","year":"2020","unstructured":"Peter Manohar and Jalani Williams. Lower bounds for caching with delayed hits. arXiv preprint arXiv:2006.00376, 2020."},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01759073"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/2786.2793"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1109\/TON.2025.3549289"},{"key":"e_1_3_2_1_35_1","first-page":"804","volume-title":"2022 USENIX Annual Technical Conference (USENIX ATC 22)","author":"Yan Gang","year":"2022","unstructured":"Gang Yan and Jian Li. Towards latency awareness for content delivery network caching. In 2022 USENIX Annual Technical Conference (USENIX ATC 22), pages 789\u2013804, 2022."},{"key":"e_1_3_2_1_36_1","volume-title":"Proceedings of the Second Annual ACM\/SIGACT-SIAM Symposium on Discrete Algorithms, 28\u201330","author":"Young Neal E.","year":"1991","unstructured":"Neal E. Young. On-line caching as cache size varies. In Alok Aggarwal, editor, Proceedings of the Second Annual ACM\/SIGACT-SIAM Symposium on Discrete Algorithms, 28\u201330 January 1991, San Francisco, California, USA, pages 241\u2013250. ACM\/SIAM, 1991."},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01189992"},{"key":"e_1_3_2_1_38_1","first-page":"86","volume-title":"Symposium on Discrete algorithms","author":"Young Neal E.","year":"1998","unstructured":"Neal E. Young. On-line file caching. In Symposium on Discrete algorithms, pages 82\u201386, 1998."}],"event":{"name":"SPAA '26: 38th ACM Symposium on Parallelism in Algorithms and Architectures","location":"Royal Holloway, University of London London United Kingdom","acronym":"SPAA '26","sponsor":["SIGARCH ACM Special Interest Group on Computer Architecture","SIGACT ACM Special Interest Group on Algorithms and Computation Theory","EATCS"]},"container-title":["Proceedings of the 38th ACM Symposium on Parallelism in Algorithms and Architectures"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3816782.3819196","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,7,8]],"date-time":"2026-07-08T17:30:18Z","timestamp":1783531818000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3816782.3819196"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,7,6]]},"references-count":38,"alternative-id":["10.1145\/3816782.3819196","10.1145\/3816782"],"URL":"https:\/\/doi.org\/10.1145\/3816782.3819196","relation":{},"subject":[],"published":{"date-parts":[[2026,7,6]]},"assertion":[{"value":"2026-07-08","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}