{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,14]],"date-time":"2026-03-14T06:54:00Z","timestamp":1773471240681,"version":"3.50.1"},"reference-count":52,"publisher":"Springer Science and Business Media LLC","issue":"9","license":[{"start":{"date-parts":[[2024,6,13]],"date-time":"2024-06-13T00:00:00Z","timestamp":1718236800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2024,6,13]],"date-time":"2024-06-13T00:00:00Z","timestamp":1718236800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100006356","name":"University of Southern Denmark","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100006356","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2024,9]]},"abstract":"Abstract<\/jats:title>A variant of the online knapsack problem is considered in the setting of predictions. In Unit Profit Knapsack, the items have unit profit, i.e., the goal is to pack as many items as possible. For Online Unit Profit Knapsack, the competitive ratio is unbounded. In contrast, it is easy to find an optimal solution offline: Pack as many of the smallest items as possible into the knapsack. The prediction available to the online algorithm is the average size of those smallest items that fit in the knapsack. For the prediction error in this hard online problem, we use the ratio $$r=\\frac{a}{\\hat{a}}$$<\/jats:tex-math>\n \n r<\/mml:mi>\n =<\/mml:mo>\n \n a<\/mml:mi>\n \n a<\/mml:mi>\n ^<\/mml:mo>\n <\/mml:mover>\n <\/mml:mfrac>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> where a<\/jats:italic> is the actual value for this average size and $$\\hat{a}$$<\/jats:tex-math>\n \n a<\/mml:mi>\n ^<\/mml:mo>\n <\/mml:mover>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> is the prediction. We give an algorithm which is $$\\frac{e-1}{e}$$<\/jats:tex-math>\n \n \n e<\/mml:mi>\n -<\/mml:mo>\n 1<\/mml:mn>\n <\/mml:mrow>\n e<\/mml:mi>\n <\/mml:mfrac>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>-competitive, if $$r=1$$<\/jats:tex-math>\n \n r<\/mml:mi>\n =<\/mml:mo>\n 1<\/mml:mn>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, and this is best possible among online algorithms knowing a<\/jats:italic> and nothing else. More generally, the algorithm has a competitive ratio of $$\\frac{e-1}{e}r$$<\/jats:tex-math>\n \n \n \n e<\/mml:mi>\n -<\/mml:mo>\n 1<\/mml:mn>\n <\/mml:mrow>\n e<\/mml:mi>\n <\/mml:mfrac>\n r<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, if $$r \\le 1$$<\/jats:tex-math>\n \n r<\/mml:mi>\n \u2264<\/mml:mo>\n 1<\/mml:mn>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, and $$\\frac{e-r}{e}r$$<\/jats:tex-math>\n \n \n \n e<\/mml:mi>\n -<\/mml:mo>\n r<\/mml:mi>\n <\/mml:mrow>\n e<\/mml:mi>\n <\/mml:mfrac>\n r<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, if $$1 \\le r < e$$<\/jats:tex-math>\n \n 1<\/mml:mn>\n \u2264<\/mml:mo>\n r<\/mml:mi>\n <<\/mml:mo>\n e<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. Any algorithm with a better competitive ratio for some $$r<1$$<\/jats:tex-math>\n \n r<\/mml:mi>\n <<\/mml:mo>\n 1<\/mml:mn>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> will have a worse competitive ratio for some $$r>1$$<\/jats:tex-math>\n \n r<\/mml:mi>\n ><\/mml:mo>\n 1<\/mml:mn>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. To obtain a positive competitive ratio for all r<\/jats:italic>, we adjust the algorithm, resulting in a competitive ratio of $$\\frac{1}{2r}$$<\/jats:tex-math>\n \n 1<\/mml:mn>\n \n 2<\/mml:mn>\n r<\/mml:mi>\n <\/mml:mrow>\n <\/mml:mfrac>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> for $$r\\ge 1$$<\/jats:tex-math>\n \n r<\/mml:mi>\n \u2265<\/mml:mo>\n 1<\/mml:mn>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> and $$\\frac{r}{2}$$<\/jats:tex-math>\n \n r<\/mml:mi>\n 2<\/mml:mn>\n <\/mml:mfrac>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> for $$r\\le 1$$<\/jats:tex-math>\n \n r<\/mml:mi>\n \u2264<\/mml:mo>\n 1<\/mml:mn>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. We show that improving the result for any $$r< 1$$<\/jats:tex-math>\n \n r<\/mml:mi>\n <<\/mml:mo>\n 1<\/mml:mn>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> leads to a worse result for some $$r>1$$<\/jats:tex-math>\n \n r<\/mml:mi>\n ><\/mml:mo>\n 1<\/mml:mn>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>.<\/jats:p>","DOI":"10.1007\/s00453-024-01239-y","type":"journal-article","created":{"date-parts":[[2024,6,13]],"date-time":"2024-06-13T05:01:52Z","timestamp":1718254912000},"page":"2786-2821","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Online Unit Profit Knapsack with Predictions"],"prefix":"10.1007","volume":"86","author":[{"given":"Joan","family":"Boyar","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Lene M.","family":"Favrholdt","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kim S.","family":"Larsen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2024,6,13]]},"reference":[{"issue":"4","key":"1239_CR1","doi-asserted-by":"publisher","first-page":"24","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\u201312425 (2021)","journal-title":"J. ACM"},{"key":"1239_CR2","unstructured":"Purohit, M., Svitkina, Z., Kumar, R.: Improving online algorithms via ML predictions. In: 31st Annual Conference on Neural Information Processing Systems (NeurIPS), pp. 9661\u20139670. Curran Associates, Inc., Red Hook, New York (2018)"},{"key":"1239_CR3","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-24777-7","volume-title":"Knapsack Problems","author":"H Kellerer","year":"2004","unstructured":"Kellerer, H., Pferschy, U., Pisinger, D.: Knapsack Problems. Springer, Berlin, Heidelberg (2004)"},{"key":"1239_CR4","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1007\/s00224-014-9566-4","volume":"58","author":"M Cygan","year":"2016","unstructured":"Cygan, M., Je\u017c, \u0141, Sgall, J.: Online knapsack revisited. Theory Comput. Syst. 58, 153\u2013160 (2016)","journal-title":"Theory Comput. Syst."},{"key":"1239_CR5","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1007\/BF01585758","volume":"68","author":"A Marchetti-Spaccamela","year":"1995","unstructured":"Marchetti-Spaccamela, A., Vercellis, C.: Stochastic on-line knapsack problems. Math. Program. 68, 73\u2013104 (1995)","journal-title":"Math. Program."},{"key":"1239_CR6","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1016\/j.tcs.2014.01.027","volume":"527","author":"H-J B\u00f6ckenhauer","year":"2014","unstructured":"B\u00f6ckenhauer, H.-J., Komm, D., Kr\u00e1lovi\u010d, R., Rossmanith, P.: The online knapsack problem: Advice and randomization. Theoret. Comput. Sci. 527, 61\u201372 (2014)","journal-title":"Theoret. Comput. Sci."},{"issue":"2","key":"1239_CR7","first-page":"19","volume":"50","author":"J Boyar","year":"2017","unstructured":"Boyar, J., Favrholdt, L.M., Kudahl, C., Larsen, K.S., Mikkelsen, J.W.: Online algorithms with advice: a survey. ACM Comput. Surv. 50(2), 19\u201311934 (2017)","journal-title":"ACM Comput. Surv."},{"key":"1239_CR8","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-42749-2","volume-title":"An Introduction to Online Computation","author":"D Komm","year":"2016","unstructured":"Komm, D.: An Introduction to Online Computation. Springer, Berlin, Heidelberg (2016)"},{"key":"1239_CR9","doi-asserted-by":"crossref","unstructured":"Zeynali, A., Sun, B., Hajiesmaili, M.H., Wierman, A.: Data-driven competitive algorithms for online knapsack and set cover. In: 35th AAAI conference on artificial intelligence (AAAI), 10833\u201310841. AAAI Press, Palo Alto, California (2021)","DOI":"10.1609\/aaai.v35i12.17294"},{"key":"1239_CR10","doi-asserted-by":"crossref","unstructured":"Zhou, Y., Chakrabarty, D., Lukose, R.M.: Budget constrained bidding in keyword auctions and online knapsack problems. In: 4th international workshop on internet and network economics (WINE). Lecture Notes in Computer Science, vol. 5385, pp. 566\u2013576. Springer, Berlin, Heidelberg (2008)","DOI":"10.1007\/978-3-540-92185-1_63"},{"key":"1239_CR11","unstructured":"Im, S., Kumar, R., Qaem, M.M., Purohit, M.: Online knapsack with frequency predictions. In: Pre-Proceedings of the 34th annual conference on neural information processing systems (NeurIPS), 2733\u20132743. Curran Associates, Inc., Red Hook, New York (2021)"},{"key":"1239_CR12","first-page":"463","volume":"8","author":"J Boyar","year":"2001","unstructured":"Boyar, J., Favrholdt, L.M., Larsen, K.S., Nielsen, M.N.: The competitive ratio for on-line dual bin packing with restricted input sequences. Nordic J. Comput. 8, 463\u2013472 (2001)","journal-title":"Nordic J. Comput."},{"key":"1239_CR13","unstructured":"Angelopoulos, S., D\u00fcrr, C., Jin, S., Kamali, S., Renault, M.P.: Online computation with untrusted advice. In: 11th Innovations in Theoretical Computer Science Conference (ITCS). LIPIcs, vol. 151, pp. 52\u201315215. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, Saarbr\u00fccken\/Wadern (2020)"},{"key":"1239_CR14","doi-asserted-by":"publisher","first-page":"1111","DOI":"10.1613\/jair.1.14820","volume":"78","author":"S Angelopoulos","year":"2023","unstructured":"Angelopoulos, S., Kamali, S., Shadkami, K.: Online bin packing with predictions. J. Artif. Intell. Res. 78, 1111\u20131141 (2023)","journal-title":"J. Artif. Intell. Res."},{"key":"1239_CR15","unstructured":"Lykouris, T., Vassilvitskii, S.: Competitive caching with machine learned advice. In: 35th international conference on machine learning (ICML), 80, 3302\u20133311. PMLR, London (2018)"},{"key":"1239_CR16","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2023.105091","volume":"295","author":"S Angelopoulos","year":"2023","unstructured":"Angelopoulos, S.: Online search with a hint. Inf. Comput. 295, 105091 (2023)","journal-title":"Inf. Comput."},{"key":"1239_CR17","doi-asserted-by":"crossref","unstructured":"Angelopoulos, S., Kamali, S., Zhang, D.: Online search with best-price and query-based predictions. In: 36th AAAI conference on artificial intelligence, 36, 9652\u20139660 (2022)","DOI":"10.1609\/aaai.v36i9.21199"},{"key":"1239_CR18","unstructured":"Bhaskara, A., Cutkosky, A., Kumar, R., Purohit, M.: Online learning with imperfect hints. In: 37th International Conference on Machine Learning (ICML). Proceedings of machine learning research, vol. 119, pp. 822\u2013831. PMLR, London (2020)"},{"issue":"1","key":"1239_CR19","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1145\/3508467.3508473","volume":"1","author":"R Lee","year":"2021","unstructured":"Lee, R., Maghakian, J., Hajiesmaili, M.H., Li, J., Sitaraman, R.K., Liu, Z.: Online peak-aware energy scheduling with untrusted advice. ACM SIGEnergy Inf. Rev. 1(1), 59\u201377 (2021)","journal-title":"ACM SIGEnergy Inf. Rev."},{"key":"1239_CR20","unstructured":"Medina, A.M., Vassilvitskii, S.: Revenue optimization with approximate bid predictions. In: 30th annual conference on neural information processing systems (NIPS), pp. 1858\u20131866. Curran Associates, Inc., Red Hook, New York (2017)"},{"key":"1239_CR21","first-page":"44","volume":"24","author":"S Ahmadian","year":"2023","unstructured":"Ahmadian, S., Esfandiari, H., Mirrokni, V., Peng, B.: Robust load balancing with machine learned advice. J. Mach. Learn. Res. 24, 44\u201314446 (2023)","journal-title":"J. Mach. Learn. Res."},{"key":"1239_CR22","doi-asserted-by":"publisher","first-page":"396","DOI":"10.1613\/jair.1.14117","volume":"77","author":"S Angelopoulos","year":"2023","unstructured":"Angelopoulos, S., Kamali, S.: Contract scheduling with predictions. J. Artif. Intell. Res. 77, 396\u2013426 (2023)","journal-title":"J. Artif. Intell. Res."},{"key":"1239_CR23","doi-asserted-by":"crossref","unstructured":"Azar, Y., Leonardi, S., Touitou, N.: Flow time scheduling with uncertain processing time. In: 53rd Annual ACM SIGACT symposium on theory of computing (STOC), 1070\u20131080. ACM, New York (2021)","DOI":"10.1145\/3406325.3451023"},{"key":"1239_CR24","doi-asserted-by":"crossref","unstructured":"Azar, Y., Leonardi, S., Touitou, N.: Distortion-oblivious algorithms for minimizing flow time. In: 33rd ACM-SIAM symposium on discrete algorithms (SODA), 252\u2013274. SIAM, Philadelphia (2022)","DOI":"10.1137\/1.9781611977073.13"},{"key":"1239_CR25","unstructured":"Balkanski, E., Gkatzelis, V., Tan, X.: Strategyproof scheduling with predictions. In: Kalai, Y.T. (ed.) 14th Innovations in Theoretical Computer Science Conference (ITCS) 2023. LIPIcs, vol. 251, pp. 11\u201311122. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, Saarbr\u00fccken\/Wadern (2023)"},{"key":"1239_CR26","doi-asserted-by":"crossref","unstructured":"Boyar, J., Favrholdt, L.M., Kamali, S., Larsen, K.S.: Online interval scheduling with predictions. In: 18th international symposium on algorithms and data structures (WADS). Lecture Notes in Computer Science, vol. 14079, pp. 193\u2013207. Springer, Berlin, Heidelberg (2023)","DOI":"10.1007\/978-3-031-38906-1_14"},{"key":"1239_CR27","unstructured":"Bamas, E., Maggiori, A., Rohwedder, L., Svensson, O.: Learning augmented energy minimization via speed scaling. In: 33rd annual conference on neural information processing systems (NeurIPS), 15350\u201315359. Curran Associates, Inc., Red Hook, New York (2020)"},{"key":"1239_CR28","doi-asserted-by":"crossref","unstructured":"Im, S., Kumar, R., Qaem, M.M., Purohit, M.: Non-clairvoyant scheduling with predictions. ACM Trans. Parallel Comput. 10(4), 19:1\u201319:26 (2022)","DOI":"10.1145\/3593969"},{"issue":"8","key":"1239_CR29","doi-asserted-by":"publisher","first-page":"1126","DOI":"10.3844\/jcssp.2018.1126.1133","volume":"14","author":"A Kumar","year":"2018","unstructured":"Kumar, A., Alam, B.: Task scheduling in real time systems with energy harvesting and energy minimization. J. Comput. Sci. 14(8), 1126\u20131133 (2018)","journal-title":"J. Comput. Sci."},{"key":"1239_CR30","doi-asserted-by":"crossref","unstructured":"Lattanzi, S., Lavastida, T., Moseley, B., Vassilvitskii, S.: Online scheduling via learned weights. In: 31st ACM-SIAM symposium on discrete algorithms (SODA), 1859\u20131877. SIAM, Philadelphia (2020)","DOI":"10.1137\/1.9781611975994.114"},{"key":"1239_CR31","unstructured":"Li, S., Xian, J.: Online unrelated machine load balancing with predictions revisited. In: 38th International Conference on Machine Learning (ICML). Proceedings of Machine Learning Research, vol. 139, pp. 6523\u20136532. PMLR, London (2021)"},{"key":"1239_CR32","unstructured":"Mitzenmacher, M.: Scheduling with Predictions and the Price of Misprediction. In: 11th Innovations in Theoretical Computer Science Conference (ITCS). LIPIcs, vol. 151, pp. 14\u201311418. Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik, Saarbr\u00fccken\/Wadern (2020)"},{"key":"1239_CR33","unstructured":"Gollapudi, S., Panigrahi, D.: Online algorithms for rent-or-buy with expert advice. In: 36th international conference on machine learning (ICML). Proceedings of Machine Learning Research, vol. 97, pp. 2319\u20132327. PMLR, London (2019)"},{"key":"1239_CR34","unstructured":"Kodialam, R.: Optimal algorithms for ski rental with soft machine-learned predictions. ArXiv (2019). arXiv:1903.00092 [cs.DS]"},{"key":"1239_CR35","unstructured":"Wang, S., Li, J.: Online algorithms for multi-shop ski rental with machine learned predictions. In: 19th international conference on autonomous agents and multiagent systems (AAMAS), 2035\u20132037. International Foundation for Autonomous Agents and Multiagent Systems, Liverpool (2020)"},{"key":"1239_CR36","doi-asserted-by":"crossref","unstructured":"Bansal, N., Coester, C., Kumar, R., Purohit, M., Vee, E.: Learning-augmented weighted paging. In: 33rd ACM-SIAM Symposium on Discrete Algorithms (SODA), 67\u201389. SIAM, Philadelphia (2022)","DOI":"10.1137\/1.9781611977073.4"},{"key":"1239_CR37","unstructured":"Indyk, P., Mallmann-Trenn, F., Mitrovic, S., Rubinfeld, R.: Online page migration with ML advice. In: 25th international conference on artificial intelligence and statistics (AISTATS). Proceedings of Machine Learning Research, vol. 151, pp. 1655\u20131670. PMLR, London (2022)"},{"key":"1239_CR38","doi-asserted-by":"crossref","unstructured":"Jiang, Z., Panigrahi, D., Sun, K.: Online algorithms for weighted paging with predictions. ACM Trans. Algorithms 18(4), 39:1\u201339:27 (2022)","DOI":"10.1145\/3548774"},{"key":"1239_CR39","doi-asserted-by":"crossref","unstructured":"Rohatgi, D.: Near-optimal bounds for online caching with machine learned advice. In: 31st ACM-SIAM symposium on discrete algorithms (SODA), 1834\u20131845. SIAM, Philadelphia (2020)","DOI":"10.1137\/1.9781611975994.112"},{"key":"1239_CR40","unstructured":"Wei, A.: Better and simpler learning-augmented online caching. In: approximation, randomization, and combinatorial optimization. algorithms and techniques (APPROX\/RANDOM). LIPIcs, vol. 176, pp. 60\u201316017. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, Saarbr\u00fccken\/Wadern (2020)"},{"issue":"2","key":"1239_CR41","doi-asserted-by":"publisher","first-page":"19","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\u201311934 (2023)","journal-title":"ACM Trans. Algorithms"},{"key":"1239_CR42","doi-asserted-by":"publisher","DOI":"10.1016\/j.disopt.2023.100778","volume":"48","author":"A Antoniadis","year":"2023","unstructured":"Antoniadis, A., Gouleakis, T., Kleer, P., Kolev, P.: Secretary and online matching problems with machine learned advice. Discrete Optim. 48, 100778 (2023)","journal-title":"Discrete Optim."},{"key":"1239_CR43","doi-asserted-by":"crossref","unstructured":"Banerjee, S., Gkatzelis, V., Gorokh, A., Jin, B.: Online Nash social welfare maximization with predictions. In: 33rd ACM-SIAM symposium on discrete algorithms (SODA),1\u201319. SIAM, Philadelphia (2022)","DOI":"10.1137\/1.9781611977073.1"},{"key":"1239_CR44","doi-asserted-by":"crossref","unstructured":"Mitzenmacher, M.: Queues with small advice. In: SIAM conference on applied and computational discrete algorithms (ACDA), 1\u201312. SIAM, Philadelphia (2021)","DOI":"10.1137\/1.9781611976830.1"},{"issue":"2","key":"1239_CR45","doi-asserted-by":"publisher","first-page":"24","DOI":"10.1145\/3512798.3512808","volume":"49","author":"D Rutten","year":"2022","unstructured":"Rutten, D., Mukherjee, D.: Capacity scaling augmented with unreliable machine learning predictions. SIGMETRICS Perform. Eval. Rev. 49(2), 24\u201326 (2022)","journal-title":"SIGMETRICS Perform. Eval. Rev."},{"key":"1239_CR46","doi-asserted-by":"crossref","unstructured":"Azar, Y., Panigrahi, D., Touitou, N.: Online graph algorithms with predictions. In: 33rd ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 35\u201366. SIAM, Philadelphia (2022)","DOI":"10.1137\/1.9781611977073.3"},{"key":"1239_CR47","unstructured":"Bamas, E., Maggiori, A., Svensson, O.: The primal-dual method for learning augmented algorithms. In: 33rd annual conference on neural information processing systems (NeurIPS), pp. 20083\u201320094. Curran Associates, Inc., Red Hook, New York (2020)"},{"key":"1239_CR48","unstructured":"Lavastida, T., Moseley, B., Ravi, R., Xu, C.: Learnable and instance-robust predictions for online matching, flows and load balancing. In: 29th Annual European Symposium on Algorithms (ESA). LIPIcs, vol. 204, pp. 59\u201315917. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, Saarbr\u00fccken\/Wadern (2021)"},{"key":"1239_CR49","unstructured":"Wei, A., Zhang, F.: Optimal robustness-consistency trade-offs for learning-augmented online algorithms. In: 33rd annual conference on neural information processing systems (NeurIPS) (2020)"},{"key":"1239_CR50","first-page":"646","volume-title":"Beyond the Worst-Case Analysis of Algorithms","author":"M Mitzenmacher","year":"2021","unstructured":"Mitzenmacher, M., Vassilvitskii, S.: Algorithms with predictions. In: Roughgarden, T. (ed.) Beyond the Worst-Case Analysis of Algorithms, pp. 646\u2013662. Cambridge University Press, Cambridge (2021)"},{"issue":"8","key":"1239_CR51","doi-asserted-by":"publisher","first-page":"2006","DOI":"10.1007\/s00224-018-9862-5","volume":"62","author":"S Angelopoulos","year":"2018","unstructured":"Angelopoulos, S., D\u00fcrr, C., Kamali, S., Renault, M.P., Ros\u00e9n, A.: Online bin packing with advice of small size. Theory Comput. Syst. 62(8), 2006\u20132034 (2018)","journal-title":"Theory Comput. Syst."},{"key":"1239_CR52","doi-asserted-by":"crossref","unstructured":"Christ, M.G., Favrholdt, L.M., Larsen, K.S.: Online Multi-Coloring with Advice. Theoret. Comput. Sci. 596, 79\u201391 (2015)","DOI":"10.1016\/j.tcs.2015.06.044"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-024-01239-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-024-01239-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-024-01239-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T07:05:26Z","timestamp":1725433526000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-024-01239-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,6,13]]},"references-count":52,"journal-issue":{"issue":"9","published-print":{"date-parts":[[2024,9]]}},"alternative-id":["1239"],"URL":"https:\/\/doi.org\/10.1007\/s00453-024-01239-y","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,6,13]]},"assertion":[{"value":"11 July 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"14 May 2024","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"13 June 2024","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 relevant financial or non-financial interests to disclose.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}