{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,12]],"date-time":"2026-06-12T15:46:09Z","timestamp":1781279169537,"version":"3.54.1"},"reference-count":55,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2023,4,15]],"date-time":"2023-04-15T00:00:00Z","timestamp":1681516800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"DFG","award":["AN 1262\/1-1"],"award-info":[{"award-number":["AN 1262\/1-1"]}]},{"name":"NWO VICI","award":["639.023.812"],"award-info":[{"award-number":["639.023.812"]}]},{"name":"ERC","award":["759471"],"award-info":[{"award-number":["759471"]}]},{"name":"National Science Center of Poland","award":["2017\/27\/N\/ST6\/01334"],"award-info":[{"award-number":["2017\/27\/N\/ST6\/01334"]}]},{"DOI":"10.13039\/501100001711","name":"Swiss National Science Foundation","doi-asserted-by":"crossref","award":["185030"],"award-info":[{"award-number":["185030"]}],"id":[{"id":"10.13039\/501100001711","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Bertrand Simon","award":["146371743"],"award-info":[{"award-number":["146371743"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2023,4,30]]},"abstract":"<jats:p>\n            Machine-learned predictors, although achieving very good results for inputs resembling training data, cannot possibly provide perfect predictions in all situations. Still, decision-making systems that are based on such predictors need not only benefit from good predictions, but should also achieve a decent performance when the predictions are inadequate. In this article, we propose a prediction setup for arbitrary\n            <jats:italic>metrical task systems (MTS)<\/jats:italic>\n            (e.g.,\u00a0\n            <jats:italic>caching<\/jats:italic>\n            ,\n            <jats:italic>\n              <jats:italic>k<\/jats:italic>\n              -server,\n            <\/jats:italic>\n            and\n            <jats:italic>convex body chasing<\/jats:italic>\n            ) and\n            <jats:italic>online matching on the line<\/jats:italic>\n            . We utilize results from the theory of online algorithms to show how to make the setup robust. Specifically, for caching, we present an algorithm whose performance, as a function of the prediction error, is exponentially better than what is achievable for general MTS. Finally, we present an empirical evaluation of our methods on real-world datasets, which suggests practicality.\n          <\/jats:p>","DOI":"10.1145\/3582689","type":"journal-article","created":{"date-parts":[[2023,2,22]],"date-time":"2023-02-22T12:20:22Z","timestamp":1677068422000},"page":"1-34","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":15,"title":["Online Metric Algorithms with Untrusted Predictions"],"prefix":"10.1145","volume":"19","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-2152-7883","authenticated-orcid":false,"given":"Antonios","family":"Antoniadis","sequence":"first","affiliation":[{"name":"University of Twente, NB, Netherlands"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3744-0977","authenticated-orcid":false,"given":"Christian","family":"Coester","sequence":"additional","affiliation":[{"name":"University of Oxford, Oxford, United Kingdom"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4583-8897","authenticated-orcid":false,"given":"Marek","family":"Eli\u00e1\u0161","sequence":"additional","affiliation":[{"name":"Bocconi University, Italy"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4925-774X","authenticated-orcid":false,"given":"Adam","family":"Polak","sequence":"additional","affiliation":[{"name":"Max Planck Institute for Informatics, Germany and Jagiellonian University, Krak\u00f3w, Poland"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2565-1163","authenticated-orcid":false,"given":"Bertrand","family":"Simon","sequence":"additional","affiliation":[{"name":"IN2P3 Computing Center, CNRS, France"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2023,4,15]]},"reference":[{"key":"e_1_3_4_2_2","first-page":"303","volume-title":"Proceedings of the International Conference on Machine Learning","author":"Anand Keerti","year":"2020","unstructured":"Keerti Anand, Rong Ge, and Debmalya Panigrahi. 2020. Customizing ML predictions for online algorithms. In Proceedings of the International Conference on Machine Learning. PMLR, 303\u2013313."},{"key":"e_1_3_4_3_2","doi-asserted-by":"publisher","DOI":"10.1145\/2566486.2568018"},{"key":"e_1_3_4_4_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ITCS.2020.52"},{"key":"e_1_3_4_5_2","volume-title":"Proceedings of the Conference on Neural Information Processing Systems (NeurIPS\u201920","author":"Antoniadis Antonios","year":"2020","unstructured":"Antonios Antoniadis, Themis Gouleakis, Pieter Kleer, and Pavel Kolev. 2020. Secretary and online matching problems with machine learned advice. In Proceedings of the Conference on Neural Information Processing Systems (NeurIPS\u201920)."},{"key":"e_1_3_4_6_2","doi-asserted-by":"publisher","DOI":"10.1145\/2339123.2339126"},{"key":"e_1_3_4_7_2","volume-title":"Proceedings of the 33rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201922)","author":"Bansal Nikhil","year":"2022","unstructured":"Nikhil Bansal, Christian Coester, Ravi Kumar, Manish Purohit, and Erik Vee. 2022. Learning-augmented weighted paging. In Proceedings of the 33rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201922)."},{"key":"e_1_3_4_8_2","doi-asserted-by":"publisher","DOI":"10.1147\/sj.52.0078"},{"key":"e_1_3_4_9_2","series-title":"Proceedings of the Conference on Web and Internet Economics","first-page":"220","volume":"12495","author":"Bender Max","year":"2020","unstructured":"Max Bender, Jacob Gilbert, Aditya Krishnan, and Kirk Pruhs. 2020. Competitively pricing parking in a tree. In Proceedings of the Conference on Web and Internet Economics(Lecture Notes in Computer Science, Vol. 12495). Springer, 220\u2013233."},{"key":"e_1_3_4_10_2","series-title":"Proceedings of the Fundamentals of Computation Theory Conference","first-page":"67","volume":"12867","author":"Bender Max","year":"2021","unstructured":"Max Bender, Jacob Gilbert, and Kirk Pruhs. 2021. A poly-log competitive posted-price algorithm for online metrical matching on a spider. In Proceedings of the Fundamentals of Computation Theory Conference(Lecture Notes in Computer Science, Vol. 12867). Springer, 67\u201384."},{"key":"e_1_3_4_11_2","doi-asserted-by":"publisher","DOI":"10.1023\/A:1007621832648"},{"key":"e_1_3_4_12_2","doi-asserted-by":"publisher","DOI":"10.5555\/290169"},{"key":"e_1_3_4_13_2","doi-asserted-by":"publisher","DOI":"10.1145\/146585.146588"},{"key":"e_1_3_4_14_2","doi-asserted-by":"publisher","DOI":"10.1145\/3056461"},{"key":"e_1_3_4_15_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975482.6"},{"key":"e_1_3_4_16_2","series-title":"Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques Conference (APPROX-RANDOM\u201920)","first-page":"54:1\u201354:14","volume":"176","author":"Bubeck S\u00e9bastien","year":"2020","unstructured":"S\u00e9bastien Bubeck and Yuval Rabani. 2020. Parametrized metrical task systems. In Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques Conference (APPROX-RANDOM\u201920)(LIPIcs, Vol. 176). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 54:1\u201354:14."},{"key":"e_1_3_4_17_2","series-title":"Proceedings of the 38th International Conference on Machine Learning","first-page":"1920","volume":"139","author":"Ch\u0142\u0119dowski Jakub","year":"2021","unstructured":"Jakub Ch\u0142\u0119dowski, Adam Polak, Bartosz Szabucki, and Konrad Tomasz \u017bo\u0142na. 2021. Robust learning-augmented caching: An experimental study. In Proceedings of the 38th International Conference on Machine Learning(Proceedings of Machine Learning Research, Vol. 139). PMLR, 1920\u20131930. Retrieved from https:\/\/proceedings.mlr.press\/v139\/chledowski21a.html."},{"key":"e_1_3_4_18_2","doi-asserted-by":"publisher","DOI":"10.1145\/2020408.2020579"},{"key":"e_1_3_4_19_2","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0029565"},{"key":"e_1_3_4_20_2","doi-asserted-by":"publisher","DOI":"10.1145\/180139.181097"},{"key":"e_1_3_4_21_2","unstructured":"CitiBike. 2017. Citi Bike Trip Histories. Retrieved from https:\/\/www.citibikenyc.com\/system-data."},{"key":"e_1_3_4_22_2","doi-asserted-by":"publisher","DOI":"10.1145\/3313276.3316370"},{"key":"e_1_3_4_23_2","first-page":"835","volume-title":"Proceedings of the Conference on Learning Theory (COLT\u201919)","author":"Coester Christian","year":"2019","unstructured":"Christian Coester and James R. Lee. 2019. Pure entropic regularization for metrical task systems. In Proceedings of the Conference on Learning Theory (COLT\u201919). 835\u2013848."},{"key":"e_1_3_4_24_2","first-page":"333","volume-title":"Proceedings of the Algorithmic Learning Theory Conference (ALT\u201919)","author":"Daniely Amit","year":"2019","unstructured":"Amit Daniely and Yishay Mansour. 2019. Competitive ratio vs regret minimization: Achieving the best of both worlds. In Proceedings of the Algorithmic Learning Theory Conference (ALT\u201919). 333\u2013368. Retrieved from http:\/\/proceedings.mlr.press\/v98\/daniely19a.html."},{"key":"e_1_3_4_25_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICALP.2017.126"},{"key":"e_1_3_4_26_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2010.08.007"},{"key":"e_1_3_4_27_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795279943"},{"key":"e_1_3_4_28_2","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(91)90041-V"},{"key":"e_1_3_4_29_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(05)80060-1"},{"key":"e_1_3_4_30_2","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1997.1504"},{"key":"e_1_3_4_31_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2004.10.028"},{"key":"e_1_3_4_32_2","first-page":"2319","volume-title":"Proceedings of of the International Conference on Machine Learning (ICML\u201919)","author":"Gollapudi Sreenivas","year":"2019","unstructured":"Sreenivas Gollapudi and Debmalya Panigrahi. 2019. Online algorithms for rent-or-buy with expert advice. In Proceedings of of the International Conference on Machine Learning (ICML\u201919). 2319\u20132327. Retrieved from http:\/\/proceedings.mlr.press\/v97\/gollapudi19a.html."},{"key":"e_1_3_4_33_2","doi-asserted-by":"publisher","DOI":"10.1145\/860176.860180"},{"key":"e_1_3_4_34_2","doi-asserted-by":"publisher","DOI":"10.1145\/3007787.3001146"},{"key":"e_1_3_4_35_2","volume-title":"Proceedings of the 47th International Colloquium on Automata, Languages, and Programming (ICALP\u201920)","author":"Jiang Zhihao","year":"2020","unstructured":"Zhihao Jiang, Debmalya Panigrahi, and Kevin Su. 2020. Online algorithms for weighted paging with predictions. In Proceedings of the 47th International Colloquium on Automata, Languages, and Programming (ICALP\u201920)."},{"key":"e_1_3_4_36_2","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1993.1026"},{"key":"e_1_3_4_37_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539792224838"},{"key":"e_1_3_4_38_2","doi-asserted-by":"publisher","DOI":"10.24963\/ijcai.2017\/92"},{"key":"e_1_3_4_39_2","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(94)90042-6"},{"key":"e_1_3_4_40_2","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3196909"},{"key":"e_1_3_4_41_2","first-page":"1859","volume-title":"Proceedings of the 31st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201920)","author":"Lattanzi Silvio","year":"2020","unstructured":"Silvio Lattanzi, Thomas Lavastida, Benjamin Moseley, and Sergei Vassilvitskii. 2020. Online scheduling via learned weights. In Proceedings of the 31st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201920). 1859\u20131877."},{"key":"e_1_3_4_42_2","article-title":"Lower bounds for MTS","author":"Lee James R.","year":"2018","unstructured":"James R. Lee. 2018. Lower bounds for MTS. Lecture notes. Retrieved from https:\/\/tcsmath.github.io\/online\/2018\/04\/20\/mts-lower-bounds\/.","journal-title":"Lecture notes"},{"key":"e_1_3_4_43_2","doi-asserted-by":"publisher","DOI":"10.1109\/TNET.2012.2226216"},{"key":"e_1_3_4_44_2","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1994.1009"},{"key":"e_1_3_4_45_2","series-title":"Proceedings of the 37th International Conference on Machine Learning","first-page":"6237","volume":"119","author":"Liu Evan","year":"2020","unstructured":"Evan Liu, Milad Hashemi, Kevin Swersky, Parthasarathy Ranganathan, and Junwhan Ahn. 2020. An imitation learning approach for cache replacement. In Proceedings of the 37th International Conference on Machine Learning(Proceedings of Machine Learning Research, Vol. 119). PMLR, 6237\u20136247. Retrieved from https:\/\/proceedings.mlr.press\/v119\/liu20f.html."},{"key":"e_1_3_4_46_2","first-page":"3302","volume-title":"Proceedings of the International Conference on Machine Learning (ICML\u201918)","author":"Lykouris Thodoris","year":"2018","unstructured":"Thodoris Lykouris and Sergei Vassilvitskii. 2018. Competitive caching with machine learned advice. In Proceedings of the International Conference on Machine Learning (ICML\u201918). 3302\u20133311. Retrieved from http:\/\/proceedings.mlr.press\/v80\/lykouris18a.html."},{"key":"e_1_3_4_47_2","doi-asserted-by":"publisher","DOI":"10.1145\/2071379.2071381"},{"key":"e_1_3_4_48_2","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(90)90003-W"},{"key":"e_1_3_4_49_2","first-page":"1858","volume-title":"Proceedings of the Conference on Neural Information Processing Systems (NeurIPS\u201917)","author":"Medina Andres Mu\u00f1oz","year":"2017","unstructured":"Andres Mu\u00f1oz Medina and Sergei Vassilvitskii. 2017. Revenue optimization with approximate bid predictions. In Proceedings of the Conference on Neural Information Processing Systems (NeurIPS\u201917). 1858\u20131866."},{"key":"e_1_3_4_50_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ITCS.2020.14"},{"key":"e_1_3_4_51_2","first-page":"9684","volume-title":"Proceedings of the Conference on Neural Information Processing Systems (NeurIPS\u201918)","author":"Purohit Manish","year":"2018","unstructured":"Manish Purohit, Zoya Svitkina, and Ravi Kumar. 2018. Improving online algorithms via ML predictions. In Proceedings of the Conference on Neural Information Processing Systems (NeurIPS\u201918). 9684\u20139693."},{"key":"e_1_3_4_52_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.SoCG.2018.67"},{"key":"e_1_3_4_53_2","first-page":"1834","volume-title":"Proceedings of the 31st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201920)","author":"Rohatgi Dhruv","year":"2020","unstructured":"Dhruv Rohatgi. 2020. Near-optimal bounds for online caching with machine learned advice. In Proceedings of the 31st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201920). 1834\u20131845."},{"key":"e_1_3_4_54_2","doi-asserted-by":"publisher","DOI":"10.1145\/3352460.3358319"},{"key":"e_1_3_4_55_2","doi-asserted-by":"publisher","DOI":"10.1145\/2786.2793"},{"key":"e_1_3_4_56_2","volume-title":"Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques Conference (APPROX\/RANDOM\u201920)","author":"Wei Alexander","year":"2020","unstructured":"Alexander Wei. 2020. Better and simpler learning-augmented online caching. In Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques Conference (APPROX\/RANDOM\u201920)."}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3582689","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3582689","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T18:09:15Z","timestamp":1750183755000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3582689"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,4,15]]},"references-count":55,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2023,4,30]]}},"alternative-id":["10.1145\/3582689"],"URL":"https:\/\/doi.org\/10.1145\/3582689","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,4,15]]},"assertion":[{"value":"2020-08-24","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-01-17","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-04-15","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}