{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,21]],"date-time":"2025-09-21T00:06:32Z","timestamp":1758413192934,"version":"3.44.0"},"reference-count":55,"publisher":"Springer Science and Business Media LLC","issue":"11","license":[{"start":{"date-parts":[[2025,7,10]],"date-time":"2025-07-10T00:00:00Z","timestamp":1752105600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2025,7,10]],"date-time":"2025-07-10T00:00:00Z","timestamp":1752105600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100007837","name":"Universit\u00e4t Bremen","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100007837","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2025,11]]},"abstract":"<jats:title>Abstract<\/jats:title>\n          <jats:p>We study the online <jats:bold>\n              <jats:italic>k<\/jats:italic>\n            <\/jats:bold>-server problem in a learning-augmented setting. While in the traditional online model, an algorithm has no information about the request sequence, we assume that there is given some advice (for example, machine-learned predictions) on an algorithm\u2019s decision. There is, however, no guarantee on the quality of the prediction, and it might be far from being correct. Our main result is a learning-augmented variation of the well-known Double Coverage algorithm for <jats:bold>\n              <jats:italic>k<\/jats:italic>\n            <\/jats:bold>-server on the line\u00a0(Chrobak et al. in SIAM J Discret Math 4(2):172\u2013181, 1991) in which we integrate predictions as well as our trust into their quality. We give an error-dependent worst-case performance guarantee, which is a function of a user-defined confidence parameter, and which interpolates smoothly between an optimal performance in case that all predictions are correct, and the best-possible performance regardless of the prediction quality. When given good predictions, we improve upon known lower bounds for online algorithms without advice. We further show that our algorithm achieves for any <jats:bold>\n              <jats:italic>k<\/jats:italic>\n            <\/jats:bold> almost optimal guarantees, within a class of deterministic learning-augmented algorithms respecting <jats:italic>local<\/jats:italic> and <jats:italic>memoryless<\/jats:italic> properties. Our algorithm outperforms a previously proposed (more general) learning-augmented algorithm. It is noteworthy that the previous algorithm crucially exploits memory, whereas our algorithm is <jats:italic>memoryless<\/jats:italic>. Finally, we demonstrate in experiments the practicability and the superior performance of our algorithm on real-world data.<\/jats:p>","DOI":"10.1007\/s00453-025-01333-9","type":"journal-article","created":{"date-parts":[[2025,7,10]],"date-time":"2025-07-10T09:54:49Z","timestamp":1752141289000},"page":"1477-1517","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Boosting Double Coverage for k-Server via Imperfect Predictions"],"prefix":"10.1007","volume":"87","author":[{"given":"Alexander","family":"Lindermayr","sequence":"first","affiliation":[]},{"given":"Nicole","family":"Megow","sequence":"additional","affiliation":[]},{"given":"Bertrand","family":"Simon","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2025,7,10]]},"reference":[{"issue":"4","key":"1333_CR1","doi-asserted-by":"publisher","first-page":"2626","DOI":"10.1287\/moor.2022.0225","volume":"49","author":"P Agrawal","year":"2024","unstructured":"Agrawal, P., Balkanski, E., Gkatzelis, V., Tingting, O., Tan, X.: Learning-augmented mechanism design: leveraging predictions for facility location. Math. Oper. Res. 49(4), 2626\u20132651 (2024). https:\/\/doi.org\/10.1287\/moor.2022.0225","journal-title":"Math. Oper. Res."},{"key":"1333_CR2","unstructured":"Almanza, M., Chierichetti, F., Lattanzi, S., Panconesi, A., Re, G.: Online facility location with multiple advice. In NeurIPS, 4661\u20134673 (2021). https:\/\/proceedings.neurips.cc\/paper\/2021\/hash\/250473494b245120a7eaf8b2e6b1f17c-Abstract.html"},{"key":"1333_CR3","unstructured":"Antoniadis, A., Boyar, J., Eli\u00e1s, M., Favrholdt, L.M., Hoeksma, R., Larsen, K.S., Polak, A., Simon, B.: Paging with succinct predictions. In ICML, volume 202 of proceedings of machine learning research, pages 952\u2013968. PMLR (2023). https:\/\/proceedings.mlr.press\/v202\/antoniadis23a.html"},{"key":"1333_CR4","unstructured":"Antoniadis, A., Coester, C., Eli\u00e1s, M., Polak, A., Simon, B.: Mixing predictions for online metric algorithms. In ICML, volume 202 of Proceedings of machine learning research, 969\u2013983. PMLR, (2023). https:\/\/proceedings.mlr.press\/v202\/antoniadis23b.html"},{"key":"1333_CR5","doi-asserted-by":"publisher","unstructured":"Antoniadis, A., Fischer, C., T\u00f6nnis, A.: A collection of lower bounds for online matching on the line. In LATIN, volume 10807 of lecture notes in computer science, 52\u201365. Springer, 2018. https:\/\/doi.org\/10.1007\/978-3-319-77404-6_5","DOI":"10.1007\/978-3-319-77404-6_5"},{"issue":"2","key":"1333_CR6","doi-asserted-by":"publisher","first-page":"19:1","DOI":"10.1145\/3582689","volume":"19","author":"A Antoniadis","year":"2023","unstructured":"Antoniadis, A., Coester, C., Eli\u00e1s, M., Polak, A., Simon, B.: Online metric algorithms with untrusted predictions. ACM Trans. Algorithms 19(2), 19:1-19:34 (2023). https:\/\/doi.org\/10.1145\/3582689","journal-title":"ACM Trans. Algorithms"},{"key":"1333_CR7","doi-asserted-by":"publisher","unstructured":"Azar, Y., Panigrahi, D., Touitou, N.: Online graph algorithms with predictions. In SODA, 35\u201366. SIAM (2022). https:\/\/doi.org\/10.1137\/1.9781611977073.3","DOI":"10.1137\/1.9781611977073.3"},{"key":"1333_CR8","doi-asserted-by":"publisher","unstructured":"Bampis, E., Escoffier, B., Gouleakis, T., Hahn, N., Lakis, K., Shahkarami, G., Xefteris, M.: Learning-augmented online TSP on rings, trees, flowers and (almost) everywhere else. In ESA, volume 274 of LIPIcs, pages 12:1\u201312:17. Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik, (2023). https:\/\/doi.org\/10.4230\/LIPIcs.ESA.2023.12","DOI":"10.4230\/LIPIcs.ESA.2023.12"},{"key":"1333_CR9","doi-asserted-by":"publisher","unstructured":"Banerjee, S., Cohen-Addad, V., Gupta, A., Li, Z.: Graph searching with predictions. In ITCS, volume 251 of LIPIcs, pages 12:1\u201312:24. Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik, (2023). https:\/\/doi.org\/10.4230\/LIPIcs.ITCS.2023.12","DOI":"10.4230\/LIPIcs.ITCS.2023.12"},{"key":"1333_CR10","doi-asserted-by":"publisher","unstructured":"Bansal, N., Coester, C., Kumar, R., Purohit, M., Vee, E.: Learning-augmented weighted paging. In SODA, 67\u201389. SIAM (2022). https:\/\/doi.org\/10.1137\/1.9781611977073.4","DOI":"10.1137\/1.9781611977073.4"},{"issue":"2\u20133","key":"1333_CR11","doi-asserted-by":"publisher","first-page":"337","DOI":"10.1016\/j.tcs.2004.06.001","volume":"324","author":"Y Bartal","year":"2004","unstructured":"Bartal, Y., Koutsoupias, E.: On the competitive ratio of the work function algorithm for the k-server problem. Theor. Comput. Sci. 324(2\u20133), 337\u2013345 (2004). https:\/\/doi.org\/10.1016\/j.tcs.2004.06.001","journal-title":"Theor. Comput. Sci."},{"key":"1333_CR12","unstructured":"Bernardini, G., Lindermayr, A., Marchetti-Spaccamela, A., Megow, N., Stougie, L., Sweering, M.: A universal error measure for input predictions applied to online graph problems. In NeurIPS, (2022). http:\/\/papers.nips.cc\/paper_files\/paper\/2022\/hash\/15212bd2265c4a3ab0dbc1b1982c1b69-Abstract-Conference.html"},{"key":"1333_CR13","volume-title":"Online Computation and Competitive Analysis","author":"A Borodin","year":"1998","unstructured":"Borodin, A., El-Yaniv, R.: Online Computation and Competitive Analysis. Cambridge University Press, United Kingdom (1998)"},{"key":"1333_CR14","doi-asserted-by":"publisher","unstructured":"Brand, J.v.d., Forster, S., Nazari, Y., Polak, A.: On dynamic graph algorithms with predictions. In SODA, 3534\u20133557. SIAM (2024). https:\/\/doi.org\/10.1137\/1.9781611977912.126","DOI":"10.1137\/1.9781611977912.126"},{"key":"1333_CR15","doi-asserted-by":"publisher","unstructured":"Bubeck, S., Coester, C., Rabani, Y.: Shortest paths without a map, but with an entropic regularizer. In FOCS, 1102\u20131113. IEEE (2022). https:\/\/doi.org\/10.1109\/FOCS54457.2022.00036","DOI":"10.1109\/FOCS54457.2022.00036"},{"key":"1333_CR16","doi-asserted-by":"publisher","unstructured":"Bubeck, S., Coester, C., Rabani, Y.: The randomized k-server conjecture is false! In STOC, 581\u2013594. ACM, (2023). https:\/\/doi.org\/10.1145\/3564246.3585132","DOI":"10.1145\/3564246.3585132"},{"key":"1333_CR17","doi-asserted-by":"publisher","unstructured":"Bubeck, S., Cohen, M.B., Lee, Y.T., Lee, J.R., Madry, A.: k-server via multiscale entropic regularization. In STOC, 3\u201316. ACM (2018). https:\/\/doi.org\/10.1145\/3188745.3188798","DOI":"10.1145\/3188745.3188798"},{"key":"1333_CR18","doi-asserted-by":"publisher","unstructured":"Buchbinder, N., Coester, C., (Seffi) Naor, J.: Online k-taxi via double coverage and time-reverse primal-dual. In IPCO, volume 12707 of Lecture notes in computer science, 15\u201329. Springer, (2021). https:\/\/doi.org\/10.1007\/978-3-030-73879-2_2","DOI":"10.1007\/978-3-030-73879-2_2"},{"key":"1333_CR19","doi-asserted-by":"publisher","unstructured":"Castenow, J., Feldkord, B., Knollmann, T., Malatyali, M., Meyer auf der Heide, F.: The k-server with preferences problem. In SPAA, 345\u2013356. ACM (2022). https:\/\/doi.org\/10.1145\/3490148.3538595","DOI":"10.1145\/3490148.3538595"},{"issue":"1","key":"1333_CR20","doi-asserted-by":"publisher","first-page":"14:1","DOI":"10.1145\/3365002","volume":"16","author":"A Chiplunkar","year":"2020","unstructured":"Chiplunkar, A., Vishwanathan, S.: Randomized memoryless algorithms for the weighted and the generalized k-server problems. ACM Trans. Algorithms 16(1), 14:1-14:28 (2020)","journal-title":"ACM Trans. Algorithms"},{"key":"1333_CR21","doi-asserted-by":"publisher","unstructured":"Cho, E., Myers, S.A., Leskovec, J.: Friendship and mobility: user movement in location-based social networks. In KDD, 1082\u20131090. ACM (2011). https:\/\/doi.org\/10.1145\/2020408.2020579","DOI":"10.1145\/2020408.2020579"},{"issue":"1","key":"1333_CR22","doi-asserted-by":"publisher","first-page":"144","DOI":"10.1137\/0220008","volume":"20","author":"M Chrobak","year":"1991","unstructured":"Chrobak, M., Larmore, L.L.: An optimal on-line algorithm for k-servers on trees. SIAM J. Comput. 20(1), 144\u2013148 (1991). https:\/\/doi.org\/10.1137\/0220008","journal-title":"SIAM J. Comput."},{"issue":"2","key":"1333_CR23","doi-asserted-by":"publisher","first-page":"172","DOI":"10.1137\/0404017","volume":"4","author":"M Chrobak","year":"1991","unstructured":"Chrobak, M., Karloff, H.J., Payne, T.H., Vishwanathan, S.: New results on server problems. SIAM J. Discret. Math. 4(2), 172\u2013181 (1991). https:\/\/doi.org\/10.1137\/0404017","journal-title":"SIAM J. Discret. Math."},{"issue":"1","key":"1333_CR24","doi-asserted-by":"publisher","first-page":"89","DOI":"10.1007\/s00453-024-01270-z","volume":"87","author":"M Chrobak","year":"2025","unstructured":"Chrobak, M., Haney, S., Liaee, M., Panigrahi, D., Rajaraman, R., Sundaram, R., Young, N.E.: Online paging with heterogeneous cache slots. Algorithmica 87(1), 89\u2013131 (2025). https:\/\/doi.org\/10.1007\/s00453-024-01270-z","journal-title":"Algorithmica"},{"key":"1333_CR25","doi-asserted-by":"publisher","unstructured":"Coester, C., Koutsoupias, E.: The online [CDATA[k]]$$k$$-taxi problem. In STOC, 1136\u20131147. ACM (2019). https:\/\/doi.org\/10.1145\/3313276.3316370","DOI":"10.1145\/3313276.3316370"},{"key":"1333_CR26","doi-asserted-by":"publisher","unstructured":"Coester, C., Koutsoupias, E.: Towards the k-server conjecture: a unifying potential, pushing the frontier to the circle. In ICALP, volume 198 of LIPIcs, 57:1\u201357:20. Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik, (2021). https:\/\/doi.org\/10.4230\/LIPIcs.ICALP.2021.57","DOI":"10.4230\/LIPIcs.ICALP.2021.57"},{"issue":"10","key":"1333_CR27","doi-asserted-by":"publisher","first-page":"4351","DOI":"10.1109\/TLA.2016.7786315","volume":"14","author":"ML Costa","year":"2016","unstructured":"Costa, M.L., Padilha, C., Melo, J.D., Neto, A.: Hierarchical reinforcement learning and parallel computing applied to the k-server problem. IEEE Lat. Am. Trans. 14(10), 4351\u20134357 (2016)","journal-title":"IEEE Lat. Am. Trans."},{"key":"1333_CR28","unstructured":"Dinitz, M., Im, S., Lavastida, T., Moseley, B., Vassilvitskii, S.: Faster matchings via learned duals. In NeurIPS, 10393\u201310406 (2021). https:\/\/proceedings.neurips.cc\/paper\/2021\/hash\/5616060fb8ae85d93f334e7267307664-Abstract.html"},{"key":"1333_CR29","doi-asserted-by":"publisher","unstructured":"Eberle, F., Lindermayr, A., Megow, N., N\u00f6lke, L., Schl\u00f6ter, J.: Robustification of online graph exploration methods. In AAAI, 9732\u20139740. AAAI Press (2022). https:\/\/doi.org\/10.1609\/aaai.v36i9.21208","DOI":"10.1609\/aaai.v36i9.21208"},{"key":"1333_CR30","doi-asserted-by":"publisher","unstructured":"Gkatzelis, V., Kollias, K., Sgouritsa, A., Tan, X.: Improved price of anarchy via predictions. In EC, 529\u2013557. ACM (2022). https:\/\/doi.org\/10.1145\/3490486.3538296","DOI":"10.1145\/3490486.3538296"},{"key":"1333_CR31","doi-asserted-by":"publisher","unstructured":"Henzinger, M., Saha, B., Seybold, M.P., Ye, C.: On the complexity of algorithms with predictions for dynamic graph problems. In ITCS, volume 287 of LIPIcs, 62:1\u201362:25. Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik, (2024). https:\/\/doi.org\/10.4230\/LIPIcs.ITCS.2024.62","DOI":"10.4230\/LIPIcs.ITCS.2024.62"},{"key":"1333_CR32","unstructured":"Im, S., Kumar, R., Petety, A., Purohit, M.: Parsimonious learning-augmented caching. In ICML, volume 162 of Proceedings of Machine Learning Research, 9588\u20139601. PMLR (2022). https:\/\/proceedings.mlr.press\/v162\/im22a.html"},{"key":"1333_CR33","doi-asserted-by":"publisher","unstructured":"Junior, M.L.L., Neto, A.D.D., de Melo, J.D.: The k-server problem: a reinforcement learning approach. In IJCNN, 798\u2013802. IEEE (2005). https:\/\/doi.org\/10.1109\/IJCNN.2005.1555954","DOI":"10.1109\/IJCNN.2005.1555954"},{"issue":"2","key":"1333_CR34","doi-asserted-by":"publisher","first-page":"105","DOI":"10.1016\/j.cosrev.2009.04.002","volume":"3","author":"E Koutsoupias","year":"2009","unstructured":"Koutsoupias, E.: The k-server problem. Comput. Sci. Rev. 3(2), 105\u2013118 (2009). https:\/\/doi.org\/10.1016\/j.cosrev.2009.04.002","journal-title":"Comput. Sci. Rev."},{"issue":"5","key":"1333_CR35","doi-asserted-by":"publisher","first-page":"971","DOI":"10.1145\/210118.210128","volume":"42","author":"E Koutsoupias","year":"1995","unstructured":"Koutsoupias, E., Papadimitriou, C.H.: On the k-server conjecture. J. ACM 42(5), 971\u2013983 (1995). https:\/\/doi.org\/10.1145\/210118.210128","journal-title":"J. ACM"},{"issue":"2\u20133","key":"1333_CR36","doi-asserted-by":"publisher","first-page":"347","DOI":"10.1016\/j.tcs.2004.06.002","volume":"324","author":"E Koutsoupias","year":"2004","unstructured":"Koutsoupias, E., Taylor, D.S.: The CNN problem and other k-server variants. Theor. Comput. Sci. 324(2\u20133), 347\u2013359 (2004). https:\/\/doi.org\/10.1016\/j.tcs.2004.06.002","journal-title":"Theor. Comput. Sci."},{"key":"1333_CR37","doi-asserted-by":"publisher","unstructured":"Kraska, T., Beutel, A., Chi, Ed H., Dean, J., Polyzotis, N.: The case for learned index structures. In SIGMOD Conference, 489\u2013504. ACM (2018). https:\/\/doi.org\/10.1145\/3183713.3196909","DOI":"10.1145\/3183713.3196909"},{"key":"1333_CR38","doi-asserted-by":"publisher","unstructured":"Lindermayr, A., Megow, N., Simon, B.: Double coverage with machine-learned advice. In ITCS, volume 215 of LIPIcs, 99:1\u201399:18. Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik, (2022). https:\/\/doi.org\/10.4230\/LIPIcs.ITCS.2022.99","DOI":"10.4230\/LIPIcs.ITCS.2022.99"},{"key":"1333_CR39","unstructured":"Lindermayr, A., Megow, N.: ALPS paper collection, (2023). https:\/\/algorithms-with-predictions.github.io\/"},{"key":"1333_CR40","volume-title":"Learning-augmented Online Algorithms for the 2-server Problem on the Line and Generalizations","author":"A Lindermayr","year":"2020","unstructured":"Lindermayr, A.: Learning-augmented Online Algorithms for the 2-server Problem on the Line and Generalizations. Master\u2019s thesis, University of Bremen, Germany (2020)"},{"key":"1333_CR41","doi-asserted-by":"publisher","first-page":"212","DOI":"10.1016\/j.eswa.2019.06.015","volume":"135","author":"R Lins","year":"2019","unstructured":"Lins, R., D\u00f3ria, A., de Melo, J.D.: Deep reinforcement learning applied to the k-server problem. Expert Syst. Appl. 135, 212\u2013218 (2019)","journal-title":"Expert Syst. Appl."},{"issue":"4","key":"1333_CR42","doi-asserted-by":"publisher","first-page":"24:1","DOI":"10.1145\/3447579","volume":"68","author":"T Lykouris","year":"2021","unstructured":"Lykouris, T., Vassilvitskii, S.: Competitive caching with machine learned advice. J. ACM 68(4), 24:1-24:25 (2021). https:\/\/doi.org\/10.1145\/3447579","journal-title":"J. ACM"},{"key":"1333_CR43","doi-asserted-by":"publisher","unstructured":"Mahdian, M., Nazerzadeh, H., Saberi, A.: Allocating online advertisement space with unreliable estimates. In EC, 288\u2013294. ACM (2007). https:\/\/doi.org\/10.1145\/1250910.1250952","DOI":"10.1145\/1250910.1250952"},{"key":"1333_CR44","doi-asserted-by":"publisher","unstructured":"Manasse, M.S., McGeoch, L.A., Sleator, D.D.: Competitive algorithms for on-line problems. In STOC, 322\u2013333. ACM (1988). https:\/\/doi.org\/10.1145\/62212.62243","DOI":"10.1145\/62212.62243"},{"issue":"2","key":"1333_CR45","doi-asserted-by":"publisher","first-page":"208","DOI":"10.1016\/0196-6774(90)90003-W","volume":"11","author":"MS Manasse","year":"1990","unstructured":"Manasse, M.S., McGeoch, L.A., Sleator, D.D.: Competitive algorithms for server problems. J. Algorithms 11(2), 208\u2013230 (1990). https:\/\/doi.org\/10.1016\/0196-6774(90)90003-W","journal-title":"J. Algorithms"},{"key":"1333_CR46","doi-asserted-by":"publisher","unstructured":"Mitzenmacher, M., Vassilvitskii, S.: Algorithms with predictions. In Beyond the Worst-Case Analysis of Algorithms, 646\u2013662. Cambridge University Press, (2020). https:\/\/doi.org\/10.1017\/9781108637435.037","DOI":"10.1017\/9781108637435.037"},{"key":"1333_CR47","unstructured":"Purohit, M., Svitkina, Z., Kumar, R.: Improving online algorithms via ML predictions. In NeurIPS, 9684\u20139693, (2018). https:\/\/proceedings.neurips.cc\/paper\/2018\/hash\/73a427badebe0e32caa2e1fc7530b7f3-Abstract.html"},{"key":"1333_CR48","doi-asserted-by":"publisher","unstructured":"Raghvendra, S., Sowle, R.: A scalable work function algorithm for the k-server problem. In SWAT, volume 227 of LIPIcs, 30:1\u201330:20. Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik, (2022). https:\/\/doi.org\/10.4230\/LIPIcs.SWAT.2022.30","DOI":"10.4230\/LIPIcs.SWAT.2022.30"},{"key":"1333_CR49","doi-asserted-by":"publisher","unstructured":"Rohatgi, D.: Near-optimal bounds for online caching with machine learned advice. In SODA, 1834\u20131845. SIAM (2020). https:\/\/doi.org\/10.1137\/1.9781611975994.112","DOI":"10.1137\/1.9781611975994.112"},{"key":"1333_CR50","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781107298019","volume-title":"Understanding Machine Learning - From Theory to Algorithms","author":"S Shalev-Shwartz","year":"2014","unstructured":"Shalev-Shwartz, S., Ben-David, S.: Understanding Machine Learning - From Theory to Algorithms. Cambridge University Press, United Kingdom (2014)"},{"issue":"2","key":"1333_CR51","doi-asserted-by":"publisher","first-page":"202","DOI":"10.1145\/2786.2793","volume":"28","author":"DD Sleator","year":"1985","unstructured":"Sleator, D.D., Tarjan, R.E.: Amortized efficiency of list update and paging rules. Commun. ACM 28(2), 202\u2013208 (1985). https:\/\/doi.org\/10.1145\/2786.2793","journal-title":"Commun. ACM"},{"issue":"11","key":"1333_CR52","doi-asserted-by":"publisher","first-page":"1134","DOI":"10.1145\/1968.1972","volume":"27","author":"LG Valiant","year":"1984","unstructured":"Valiant, L.G.: A theory of the learnable. Commun. ACM 27(11), 1134\u20131142 (1984). https:\/\/doi.org\/10.1145\/1968.1972","journal-title":"Commun. ACM"},{"issue":"2","key":"1333_CR53","doi-asserted-by":"publisher","first-page":"264","DOI":"10.1137\/1116025","volume":"16","author":"VN Vapnik","year":"1971","unstructured":"Vapnik, V.N., Chervonenkis, A.Y.: On the uniform convergence of relative frequencies of events to their probabilities. Theory Probab. Appl. 16(2), 264\u2013280 (1971)","journal-title":"Theory Probab. Appl."},{"key":"1333_CR54","doi-asserted-by":"publisher","unstructured":"Xu, C., Moseley, B.: Learning-augmented algorithms for online steiner tree. In AAAI, 8744\u20138752. AAAI Press (2022). https:\/\/doi.org\/10.1609\/aaai.v36i8.20854","DOI":"10.1609\/aaai.v36i8.20854"},{"issue":"2","key":"1333_CR55","doi-asserted-by":"publisher","first-page":"509","DOI":"10.1007\/s10878-019-00493-z","volume":"39","author":"W Zhang","year":"2020","unstructured":"Zhang, W., Cheng, Y.: A new upper bound on the work function algorithm for the k-server problem. J. Comb. Optim. 39(2), 509\u2013518 (2020). https:\/\/doi.org\/10.1007\/s10878-019-00493-z","journal-title":"J. Comb. Optim."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-025-01333-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-025-01333-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-025-01333-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,9,20]],"date-time":"2025-09-20T20:13:21Z","timestamp":1758399201000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-025-01333-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,7,10]]},"references-count":55,"journal-issue":{"issue":"11","published-print":{"date-parts":[[2025,11]]}},"alternative-id":["1333"],"URL":"https:\/\/doi.org\/10.1007\/s00453-025-01333-9","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2025,7,10]]},"assertion":[{"value":"25 October 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"9 June 2025","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"10 July 2025","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors have no Conflict of interest to declare that are relevant to the content of this article.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}