{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,10]],"date-time":"2026-03-10T21:54:12Z","timestamp":1773179652256,"version":"3.50.1"},"reference-count":66,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2025,3,1]],"date-time":"2025-03-01T00:00:00Z","timestamp":1740787200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2025,3,1]],"date-time":"2025-03-01T00:00:00Z","timestamp":1740787200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"Swiss Federal Institute of Technology Zurich"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2025,3]]},"abstract":"Abstract<\/jats:title>\n We analyze the competitive ratio and the advice complexity of the online unbounded knapsack problem. An instance is given as a sequence of \n n<\/jats:italic>\n <\/jats:bold> items with a size and a value each, and an algorithm has to decide whether or not and how often to pack each item into a knapsack of bounded capacity. The items are given online and the total size of the packed items must not exceed the knapsack\u2019s capacity, while the objective is to maximize the total value of the packed items. While each item can only be packed once in the classical knapsack problem (also called the 0-1 knapsack problem), the unbounded version allows for items to be packed multiple times. We show that the simple unbounded knapsack problem, where the size of each item is equal to its value, allows for a competitive ratio of 2. We also analyze randomized algorithms and show that, in contrast to the 0-1 knapsack problem, one uniformly random bit cannot improve an algorithm\u2019s performance. More randomness lowers the competitive ratio to less than 1<\/jats:bold>.736<\/jats:bold>, but it can never be below 1<\/jats:bold>.693<\/jats:bold>. In the advice complexity setting, we measure how many bits of information (so-called advice bits) the algorithm has to know to achieve some desired solution quality. For the simple unbounded knapsack problem, one advice bit lowers the competitive ratio to \n \n $$\\varvec{3\/2}$$<\/jats:tex-math>\n \n \n 3<\/mml:mn>\n \/<\/mml:mo>\n 2<\/mml:mn>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>. While this cannot be improved with fewer than \n \n $$\\varvec{\\log }_{\\varvec{2}} \\varvec{n} $$<\/jats:tex-math>\n \n \n \n \n log<\/mml:mo>\n <\/mml:mrow>\n \n 2<\/mml:mn>\n <\/mml:mrow>\n <\/mml:msub>\n \n n<\/mml:mi>\n <\/mml:mrow>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula> advice bits for instances of length \n n<\/jats:italic>\n <\/jats:bold>, a competitive ratio of \n \n $$\\varvec{1}\\varvec{+}\\varvec{\\varepsilon }$$<\/jats:tex-math>\n \n \n \n 1<\/mml:mn>\n <\/mml:mrow>\n \n +<\/mml:mo>\n <\/mml:mrow>\n \n \u03b5<\/mml:mi>\n <\/mml:mrow>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula> can be achieved with \n \n $$\\varvec{O}\\varvec{(}\\varvec{\\varepsilon }^{\\varvec{-1}} \\varvec{\\cdot }\\varvec{\\log }\\varvec{(}\\varvec{n}\\varvec{\\varepsilon }^{\\varvec{-1}}\\varvec{))}$$<\/jats:tex-math>\n \n \n \n O<\/mml:mi>\n <\/mml:mrow>\n \n (<\/mml:mo>\n <\/mml:mrow>\n \n \n \u03b5<\/mml:mi>\n <\/mml:mrow>\n \n -<\/mml:mo>\n 1<\/mml:mn>\n <\/mml:mrow>\n <\/mml:msup>\n \n \u00b7<\/mml:mo>\n <\/mml:mrow>\n \n log<\/mml:mo>\n <\/mml:mrow>\n \n (<\/mml:mo>\n <\/mml:mrow>\n \n n<\/mml:mi>\n <\/mml:mrow>\n \n \n \u03b5<\/mml:mi>\n <\/mml:mrow>\n \n -<\/mml:mo>\n 1<\/mml:mn>\n <\/mml:mrow>\n <\/mml:msup>\n \n )<\/mml:mo>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula> advice bits for any \n \n $$\\varvec{\\varepsilon }\\varvec{>}\\varvec{0}$$<\/jats:tex-math>\n \n \n \n \u03b5<\/mml:mi>\n <\/mml:mrow>\n \n ><\/mml:mo>\n <\/mml:mrow>\n \n 0<\/mml:mn>\n <\/mml:mrow>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>. We further show that no amount of advice bounded by a function \n \n $$\\varvec{f(n)}$$<\/jats:tex-math>\n \n \n f<\/mml:mi>\n (<\/mml:mo>\n n<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula> allows an algorithm to be optimal. We also study the online general unbounded knapsack problem and show that it does not allow for any bounded competitive ratio for both deterministic and randomized algorithms, as well as for algorithms using fewer than \n \n $$\\varvec{\\log }_{\\varvec{2}} \\varvec{n}$$<\/jats:tex-math>\n \n \n \n \n log<\/mml:mo>\n <\/mml:mrow>\n \n 2<\/mml:mn>\n <\/mml:mrow>\n <\/mml:msub>\n \n n<\/mml:mi>\n <\/mml:mrow>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula> advice bits. We also provide a surprisingly simple algorithm that uses \n \n $$\\varvec{O}\\varvec{(}\\varvec{\\varepsilon }^{\\varvec{-1}} \\varvec{\\cdot }\\varvec{\\log }\\varvec{(}\\varvec{n}\\varvec{\\varepsilon }^{\\varvec{-1}}\\varvec{))}$$<\/jats:tex-math>\n \n \n \n O<\/mml:mi>\n <\/mml:mrow>\n \n (<\/mml:mo>\n <\/mml:mrow>\n \n \n \u03b5<\/mml:mi>\n <\/mml:mrow>\n \n -<\/mml:mo>\n 1<\/mml:mn>\n <\/mml:mrow>\n <\/mml:msup>\n \n \u00b7<\/mml:mo>\n <\/mml:mrow>\n \n log<\/mml:mo>\n <\/mml:mrow>\n \n (<\/mml:mo>\n <\/mml:mrow>\n \n n<\/mml:mi>\n <\/mml:mrow>\n \n \n \u03b5<\/mml:mi>\n <\/mml:mrow>\n \n -<\/mml:mo>\n 1<\/mml:mn>\n <\/mml:mrow>\n <\/mml:msup>\n \n )<\/mml:mo>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula> advice bits to achieve a competitive ratio of \n \n $$\\varvec{1}\\varvec{+}\\varvec{\\varepsilon }$$<\/jats:tex-math>\n \n \n \n 1<\/mml:mn>\n <\/mml:mrow>\n \n +<\/mml:mo>\n <\/mml:mrow>\n \n \u03b5<\/mml:mi>\n <\/mml:mrow>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula> for any \n \n $$\\varvec{\\varepsilon }\\varvec{>}\\varvec{0}$$<\/jats:tex-math>\n \n \n \n \u03b5<\/mml:mi>\n <\/mml:mrow>\n \n ><\/mml:mo>\n <\/mml:mrow>\n \n 0<\/mml:mn>\n <\/mml:mrow>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>.<\/jats:p>","DOI":"10.1007\/s00224-025-10215-0","type":"journal-article","created":{"date-parts":[[2025,3,1]],"date-time":"2025-03-01T02:30:49Z","timestamp":1740796249000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Online Unbounded Knapsack"],"prefix":"10.1007","volume":"69","author":[{"given":"Hans-Joachim","family":"B\u00f6ckenhauer","sequence":"first","affiliation":[]},{"given":"Matthias","family":"Gehnen","sequence":"additional","affiliation":[]},{"given":"Juraj","family":"Hromkovi\u010d","sequence":"additional","affiliation":[]},{"given":"Ralf","family":"Klasing","sequence":"additional","affiliation":[]},{"given":"Dennis","family":"Komm","sequence":"additional","affiliation":[]},{"given":"Henri","family":"Lotze","sequence":"additional","affiliation":[]},{"given":"Daniel","family":"Mock","sequence":"additional","affiliation":[]},{"given":"Peter","family":"Rossmanith","sequence":"additional","affiliation":[]},{"given":"Moritz","family":"Stocker","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2025,3,1]]},"reference":[{"key":"10215_CR1","unstructured":"Epstein, L., Noga, J., Seiden, S.S., Sgall, J., Woeginger, G.J.: Randomized online scheduling on two uniform machines. In: Tarjan, R.E., Warnow, T.J. (eds.) Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms, 17-19 January 1999, Baltimore, Maryland, USA, pp. 317\u2013326. ACM\/SIAM, Philadelphia (1999). http:\/\/dl.acm.org\/citation.cfm?id=314500.314581"},{"issue":"5","key":"10215_CR2","doi-asserted-by":"publisher","first-page":"215","DOI":"10.1016\/S0167-6377(00)00053-5","volume":"27","author":"SS Seiden","year":"2000","unstructured":"Seiden, S.S., Sgall, J., Woeginger, G.J.: Semi-online scheduling with decreasing job sizes. Oper. Res. Lett. 27(5), 215\u2013221 (2000). https:\/\/doi.org\/10.1016\/S0167-6377(00)00053-5","journal-title":"Oper. Res. Lett."},{"issue":"6","key":"10215_CR3","doi-asserted-by":"publisher","first-page":"583","DOI":"10.1016\/J.ORL.2023.09.010","volume":"51","author":"J Sgall","year":"2023","unstructured":"Sgall, J., Woeginger, G.J.: Multiprocessor jobs, preemptive schedules, and one-competitive online algorithms. Oper. Res. Lett. 51(6), 583\u2013590 (2023). https:\/\/doi.org\/10.1016\/J.ORL.2023.09.010","journal-title":"Oper. Res. Lett."},{"issue":"2","key":"10215_CR4","doi-asserted-by":"publisher","first-page":"308","DOI":"10.1016\/S0196-6774(02)00202-X","volume":"44","author":"J Csirik","year":"2002","unstructured":"Csirik, J., Woeginger, G.J.: Resource augmentation for online bounded space bin packing. J. Algorithms 44(2), 308\u2013320 (2002). https:\/\/doi.org\/10.1016\/S0196-6774(02)00202-X","journal-title":"J. Algorithms"},{"key":"10215_CR5","doi-asserted-by":"publisher","unstructured":"Ebenlendr, T., Noga, J., Sgall, J., Woeginger, G.J.: A note on semi-online machine covering. In: Erlebach, T., Persiano, G. (eds.) Approximation and Online Algorithms, Third International Workshop, WAOA 2005, Palma de Mallorca, Spain, October 6-7, 2005, Revised Papers. Lecture Notes in Computer Science, vol. 3879, pp. 110\u2013118. Springer, Berlin Heidelberg (2005). https:\/\/doi.org\/10.1007\/11671411_9","DOI":"10.1007\/11671411_9"},{"key":"10215_CR6","doi-asserted-by":"publisher","unstructured":"Fiat, A., Woeginger, G.J. (eds.): Online Algorithms, The State of the Art. Lecture Notes in Computer Science, vol. 1442. Springer, Berlin Heidelberg (1998). https:\/\/doi.org\/10.1007\/BFb0029561","DOI":"10.1007\/BFb0029561"},{"issue":"1","key":"10215_CR7","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1016\/S0167-6377(01)00076-1","volume":"29","author":"M Zukerman","year":"2001","unstructured":"Zukerman, M., Jia, L., Neame, T.D., Woeginger, G.J.: A polynomially solvable special case of the unbounded knapsack problem. Oper. Res. Lett. 29(1), 13\u201316 (2001). https:\/\/doi.org\/10.1016\/S0167-6377(01)00076-1","journal-title":"Oper. Res. Lett."},{"issue":"2","key":"10215_CR8","doi-asserted-by":"publisher","first-page":"384","DOI":"10.1016\/j.ejor.2011.03.028","volume":"213","author":"VG Deineko","year":"2011","unstructured":"Deineko, V.G., Woeginger, G.J.: Unbounded knapsack problems with arithmetic weight sequences. Eur. J. Oper. Res. 213(2), 384\u2013387 (2011). https:\/\/doi.org\/10.1016\/j.ejor.2011.03.028","journal-title":"Eur. J. Oper. Res."},{"issue":"2","key":"10215_CR9","doi-asserted-by":"publisher","first-page":"118","DOI":"10.1016\/j.orl.2011.01.006","volume":"39","author":"VG Deineko","year":"2011","unstructured":"Deineko, V.G., Woeginger, G.J.: A well-solvable special case of the bounded knapsack problem. Oper. Res. Lett. 39(2), 118\u2013120 (2011). https:\/\/doi.org\/10.1016\/j.orl.2011.01.006","journal-title":"Oper. Res. Lett."},{"key":"10215_CR10","doi-asserted-by":"publisher","unstructured":"Karp, R.M.: Reducibility among combinatorial problems. In: Miller, R.E., Thatcher, J.W. (eds.) Proceedings of a Symposium on the Complexity of Computer Computations, pp. 85\u2013103. Plenum Press, New York (1972). https:\/\/doi.org\/10.1007\/978-1-4684-2001-2_9","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"10215_CR11","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"MR Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, New York, USA (1979)"},{"issue":"4","key":"10215_CR12","doi-asserted-by":"publisher","first-page":"463","DOI":"10.1145\/321906.321909","volume":"22","author":"OH Ibarra","year":"1975","unstructured":"Ibarra, O.H., Kim, C.E.: Fast approximation algorithms for the knapsack and sum of subset problems. J. ACM 22(4), 463\u2013468 (1975). https:\/\/doi.org\/10.1145\/321906.321909","journal-title":"J. ACM"},{"issue":"4","key":"10215_CR13","doi-asserted-by":"publisher","first-page":"339","DOI":"10.1287\/moor.4.4.339","volume":"4","author":"EL Lawler","year":"1979","unstructured":"Lawler, E.L.: Fast approximation algorithms for knapsack problems. Math. Oper. Res. 4(4), 339\u2013356 (1979). https:\/\/doi.org\/10.1287\/moor.4.4.339","journal-title":"Math. Oper. Res."},{"key":"10215_CR14","doi-asserted-by":"publisher","first-page":"270","DOI":"10.1016\/0377-2217(81)90175-2","volume":"8","author":"MJ Magazine","year":"1981","unstructured":"Magazine, M.J., Oguz, O.: A fully polynomial approximation algorithm for the 0\u20131 knapsack problem. Eur J Oper Res 8, 270\u2013273 (1981)","journal-title":"Eur J Oper Res"},{"issue":"1","key":"10215_CR15","doi-asserted-by":"publisher","first-page":"5","DOI":"10.1023\/B:JOCO.0000021934.29833.6b","volume":"8","author":"H Kellerer","year":"2004","unstructured":"Kellerer, H., Pferschy, U.: Improved dynamic programming in connection with an FPTAS for the knapsack problem. J. Comb. Optim. 8(1), 5\u201311 (2004). https:\/\/doi.org\/10.1023\/B:JOCO.0000021934.29833.6b","journal-title":"J. Comb. Optim."},{"key":"10215_CR16","doi-asserted-by":"publisher","unstructured":"Jin, C.: An improved FPTAS for 0-1 knapsack. In: Baier, C., Chatzigiannakis, I., Flocchini, P., Leonardi, S. (eds.) 46th International Colloquium on Automata, Languages, and Programming. LIPIcs, vol. 132, pp. 76:1\u201376:14. Patras, Greece (2019). https:\/\/doi.org\/10.4230\/LIPIcs.ICALP.2019.76","DOI":"10.4230\/LIPIcs.ICALP.2019.76"},{"key":"10215_CR17","doi-asserted-by":"publisher","unstructured":"Kellerer, H., Pferschy, U., Pisinger, D.: Knapsack Problems. Springer, Berlin Heidelberg (2004). https:\/\/doi.org\/10.1007\/978-3-540-24777-7","DOI":"10.1007\/978-3-540-24777-7"},{"key":"10215_CR18","doi-asserted-by":"publisher","first-page":"148","DOI":"10.1016\/j.ejc.2017.07.016","volume":"68","author":"K Jansen","year":"2018","unstructured":"Jansen, K., Kraft, S.E.J.: A faster FPTAS for the unbounded knapsack problem. Eur. J. Comb. 68, 148\u2013174 (2018). https:\/\/doi.org\/10.1016\/j.ejc.2017.07.016","journal-title":"Eur. J. Comb."},{"issue":"2","key":"10215_CR19","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"},{"key":"10215_CR20","doi-asserted-by":"publisher","unstructured":"Komm, D.: An Introduction to Online Computation - Determinism, Randomization, Advice. Texts in Theoretical Computer Science. An EATCS Series. Springer, Cham, Switzerland (2016). https:\/\/doi.org\/10.1007\/978-3-319-42749-2","DOI":"10.1007\/978-3-319-42749-2"},{"key":"10215_CR21","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, Cambridge (1998)"},{"key":"10215_CR22","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). https:\/\/doi.org\/10.1007\/BF01585758","journal-title":"Math. Program."},{"issue":"2","key":"10215_CR23","doi-asserted-by":"publisher","first-page":"277","DOI":"10.1006\/jagm.1998.0954","volume":"29","author":"GS Lueker","year":"1998","unstructured":"Lueker, G.S.: Average-case analysis of off-line and on-line knapsack problems. J. Algorithms 29(2), 277\u2013305 (1998). https:\/\/doi.org\/10.1006\/jagm.1998.0954","journal-title":"J. Algorithms"},{"key":"10215_CR24","doi-asserted-by":"publisher","unstructured":"B\u00f6ckenhauer, H.-J., Burjons, E., Hromkovi\u010d, J., Lotze, H., Rossmanith, P.: Online simple knapsack with reservation costs. In: Bl\u00e4ser, M., Monmege, B. (eds.) 38th International Symposium on Theoretical Aspects of Computer Science. LIPIcs, vol. 187, pp. 16:1\u201316:18. Saarbr\u00fccken (2021). https:\/\/doi.org\/10.4230\/LIPIcs.STACS.2021.16","DOI":"10.4230\/LIPIcs.STACS.2021.16"},{"key":"10215_CR25","doi-asserted-by":"publisher","unstructured":"Iwama, K., Taketomi, S.: Removable online knapsack problems. In: Widmayer, P., Ruiz, F.T., Bueno, R.M., Hennessy, M., Eidenbenz, S.J., Conejo, R. (eds.) Automata, Languages and Programming, 29th International Colloquium. Lecture Notes in Computer Science, vol. 2380, pp. 293\u2013305. Springer, Malaga, Spain (2002). https:\/\/doi.org\/10.1007\/3-540-45465-9_26","DOI":"10.1007\/3-540-45465-9_26"},{"issue":"1","key":"10215_CR26","doi-asserted-by":"publisher","first-page":"76","DOI":"10.1007\/S00453-013-9822-Z","volume":"70","author":"X Han","year":"2014","unstructured":"Han, X., Kawase, Y., Makino, K.: Online unweighted knapsack problem with removal cost. Algorithmica 70(1), 76\u201391 (2014). https:\/\/doi.org\/10.1007\/S00453-013-9822-Z","journal-title":"Algorithmica"},{"key":"10215_CR27","doi-asserted-by":"publisher","unstructured":"B\u00f6ckenhauer, H.-J., Klasing, R., M\u00f6mke, T., Rossmanith, P., Stocker, M., Wehner, D.: Online knapsack with removal and recourse. In: Hsieh, S.-Y., Hung, L.-J., Lee, C.-W. (eds.) Proceedings of the 34th International Workshop, IWOCA 2023. Lecture Notes in Computer Science, vol. 13889, pp. 123\u2013135. Springer, Cham, Switzerland (2023). https:\/\/doi.org\/10.1007\/978-3-031-34347-6_11","DOI":"10.1007\/978-3-031-34347-6_11"},{"key":"10215_CR28","doi-asserted-by":"publisher","unstructured":"B\u00f6ckenhauer, H.-J., Komm, D., Kr\u00e1lovi\u010d, R., Rossmanith, P.: On the advice complexity of the knapsack problem. In: Fern\u00e1ndez-Baca, D. (ed.) LATIN 2012: Theoretical Informatics - 10th Latin American Symposium. Lecture Notes in Computer Science, vol. 7256, pp. 61\u201372. Springer, Arequipa, Peru (2012). https:\/\/doi.org\/10.1007\/978-3-642-29344-3_6","DOI":"10.1007\/978-3-642-29344-3_6"},{"key":"10215_CR29","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. Theor. Comput. Sci. 527, 61\u201372 (2014). https:\/\/doi.org\/10.1016\/j.tcs.2014.01.027","journal-title":"Theor. Comput. Sci."},{"issue":"3","key":"10215_CR30","doi-asserted-by":"publisher","first-page":"585","DOI":"10.1051\/ita\/2009012","volume":"43","author":"S Dobrev","year":"2009","unstructured":"Dobrev, S., Kr\u00e1lovi\u010d, R., Pardubsk\u00e1, D.: Measuring the problem-relevant information in input. RAIRO Theor. Informatics Appl. 43(3), 585\u2013613 (2009). https:\/\/doi.org\/10.1051\/ita\/2009012","journal-title":"RAIRO Theor. Informatics Appl."},{"key":"10215_CR31","doi-asserted-by":"publisher","first-page":"2642","DOI":"10.1016\/J.TCS.2010.08.007","volume":"412","author":"Y Emek","year":"2011","unstructured":"Emek, Y., Fraigniaud, P., Korman, A., Ros\u00e9n, A.: Online computation with advice 412, 2642\u20132656 (2011). https:\/\/doi.org\/10.1016\/J.TCS.2010.08.007","journal-title":"Online computation with advice"},{"key":"10215_CR32","doi-asserted-by":"publisher","unstructured":"Hromkovi\u010d, J., Kr\u00e1lovi\u010d, R., Kr\u00e1lovi\u010d, R.: Information complexity of online problems. In: Hlinen\u00fd, P., Ku\u010der\u00e1, A. (eds.) Mathematical Foundations of Computer Science 2010, 35th International Symposium, MFCS. Lecture Notes in Computer Science, vol. 6281, pp. 24\u201336. Springer, Brno, Czech Republic (2010). https:\/\/doi.org\/10.1007\/978-3-642-15155-2_3","DOI":"10.1007\/978-3-642-15155-2_3"},{"key":"10215_CR33","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1016\/j.ic.2017.03.001","volume":"254","author":"H-J B\u00f6ckenhauer","year":"2017","unstructured":"B\u00f6ckenhauer, H.-J., Komm, D., Kr\u00e1lovi\u010d, R., Kr\u00e1lovi\u010d, R., M\u00f6mke, T.: Online algorithms with advice: The tape model. Inf. Comput. 254, 59\u201383 (2017). https:\/\/doi.org\/10.1016\/j.ic.2017.03.001","journal-title":"Inf. Comput."},{"key":"10215_CR34","doi-asserted-by":"publisher","unstructured":"B\u00f6ckenhauer, H.-J., Frei, F., Rossmanith, P.i: Removable online knapsack and advice. In: Beyersdorff, O., Kant\u00e9, M.M., Kupferman, O., Lokshtanov, D. (eds.) 41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024). LIPIcs, vol. 289, pp. 18:1\u201318:17. Saarbr\u00fccken (2024). https:\/\/doi.org\/10.4230\/LIPIcs.STACS.2024.18","DOI":"10.4230\/LIPIcs.STACS.2024.18"},{"key":"10215_CR35","doi-asserted-by":"publisher","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:1\u201319:34 (2017). https:\/\/doi.org\/10.1145\/3056461","DOI":"10.1145\/3056461"},{"issue":"4","key":"10215_CR36","doi-asserted-by":"publisher","first-page":"505","DOI":"10.1142\/S0129054118410034","volume":"29","author":"MP Bianchi","year":"2018","unstructured":"Bianchi, M.P., B\u00f6ckenhauer, H.-J., Br\u00fclisauer, T., Komm, D., Palano, B.: Online minimum spanning tree with advice. Int. J. Found. Comput. Sci. 29(4), 505\u2013527 (2018). https:\/\/doi.org\/10.1142\/S0129054118410034","journal-title":"Int. J. Found. Comput. Sci."},{"key":"10215_CR37","doi-asserted-by":"publisher","unstructured":"B\u00f6ckenhauer, H.-J., Di Caro, L., Unger, W.: Fully online matching with advice on general bipartite graphs and paths. In: B\u00f6ckenhauer, H.-J., Komm, D., Unger, W. (eds.) Adventures Between Lower Bounds and Higher Altitudes - Essays Dedicated to Juraj Hromkovi\u010d on the Occasion of His 60th Birthday. Lecture Notes in Computer Science, vol. 11011, pp. 172\u2013190. Springer, Cham, Switzerland (2018). https:\/\/doi.org\/10.1007\/978-3-319-98355-4_11","DOI":"10.1007\/978-3-319-98355-4_11"},{"key":"10215_CR38","unstructured":"Jin, B., Ma, W.: Online bipartite matching with advice: Tight robustness-consistency tradeoffs for the two-stage model. In: Koyejo, S., Mohamed, S., Agarwal, A., Belgrave, D., Cho, K., Oh, A. (eds.) Advances in Neural Information Processing Systems, vol. 35, pp. 14555\u201314567 (2022)"},{"key":"10215_CR39","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2022.101943","volume":"110","author":"AM Lavasani","year":"2023","unstructured":"Lavasani, A.M., Pankratov, D.: Advice complexity of online non-crossing matching. Comput. Geom. 110, 101943 (2023). https:\/\/doi.org\/10.1016\/j.comgeo.2022.101943","journal-title":"Comput. Geom."},{"key":"10215_CR40","doi-asserted-by":"publisher","unstructured":"Rossmanith, P.: On the advice complexity of online edge- and node-deletion problems. In: B\u00f6ckenhauer, H.-J., Komm, D., Unger, W. (eds.) Adventures Between Lower Bounds and Higher Altitudes - Essays Dedicated to Juraj Hromkovi\u010d on the Occasion of His 60th Birthday. Lecture Notes in Computer Science, vol. 11011, pp. 449\u2013462. Springer, Cham, Switzerland (2018). https:\/\/doi.org\/10.1007\/978-3-319-98355-4_26","DOI":"10.1007\/978-3-319-98355-4_26"},{"issue":"9","key":"10215_CR41","doi-asserted-by":"publisher","first-page":"2719","DOI":"10.1007\/s00453-021-00840-9","volume":"83","author":"L-H Chen","year":"2021","unstructured":"Chen, L.-H., Hung, L.-J., Lotze, H., Rossmanith, P.: Online node- and edge-deletion problems with advice. Algorithmica 83(9), 2719\u20132753 (2021). https:\/\/doi.org\/10.1007\/s00453-021-00840-9","journal-title":"Algorithmica"},{"key":"10215_CR42","doi-asserted-by":"publisher","unstructured":"Berndt, N., Lotze, H.: Advice complexity bounds for online delayed F-node-, H-node-and H-edge-deletion problems. In: Hsieh, S.-Y., Hung, L.-J., Lee, C.-W. (eds.) Proceedings of the 34th International Workshop on Combinatorial Algorithms, IWOCA 2023. Lecture Notes in Computer Science, vol. 13889, pp. 62\u201373. Springer, Cham, Switzerland (2023). https:\/\/doi.org\/10.1007\/978-3-031-34347-6_6","DOI":"10.1007\/978-3-031-34347-6_6"},{"issue":"3","key":"10215_CR43","doi-asserted-by":"publisher","first-page":"795","DOI":"10.1007\/s00453-020-00728-0","volume":"83","author":"J Boyar","year":"2021","unstructured":"Boyar, J., Favrholdt, L.M., Kamali, S., Larsen, K.S.: Online bin covering with advice. Algorithmica 83(3), 795\u2013821 (2021). https:\/\/doi.org\/10.1007\/s00453-020-00728-0","journal-title":"Algorithmica"},{"key":"10215_CR44","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1016\/j.tcs.2020.12.016","volume":"856","author":"SPY Fung","year":"2021","unstructured":"Fung, S.P.Y.: Online two-way trading: Randomization and advice. Theor. Comput. Sci. 856, 41\u201350 (2021). https:\/\/doi.org\/10.1016\/j.tcs.2020.12.016","journal-title":"Theor. Comput. Sci."},{"issue":"5","key":"10215_CR45","doi-asserted-by":"publisher","first-page":"1938","DOI":"10.1007\/s00453-018-0519-1","volume":"81","author":"J Boyar","year":"2019","unstructured":"Boyar, J., Eidenbenz, S.J., Favrholdt, L.M., Kotrbc\u00edk, M., Larsen, K.S.: Online dominating set. Algorithmica 81(5), 1938\u20131964 (2019). https:\/\/doi.org\/10.1007\/s00453-018-0519-1","journal-title":"Algorithmica"},{"key":"10215_CR46","doi-asserted-by":"publisher","first-page":"81","DOI":"10.1016\/j.tcs.2021.01.022","volume":"862","author":"H-J B\u00f6ckenhauer","year":"2021","unstructured":"B\u00f6ckenhauer, H.-J., Hromkovi\u010d, J., Krug, S., Unger, W.: On the advice complexity of the online dominating set problem. Theor. Comput. Sci. 862, 81\u201396 (2021). https:\/\/doi.org\/10.1016\/j.tcs.2021.01.022","journal-title":"Theor. Comput. Sci."},{"key":"10215_CR47","doi-asserted-by":"publisher","first-page":"77","DOI":"10.1016\/j.tcs.2022.03.022","volume":"918","author":"H-J B\u00f6ckenhauer","year":"2022","unstructured":"B\u00f6ckenhauer, H.-J., Komm, D., Wegner, R.: Call admission problems on grids with advice. Theor. Comput. Sci. 918, 77\u201393 (2022). https:\/\/doi.org\/10.1016\/j.tcs.2022.03.022","journal-title":"Theor. Comput. Sci."},{"key":"10215_CR48","doi-asserted-by":"publisher","unstructured":"Nilsson, B.J., Vujovic, G.: Online two-dimensional vector packing with advice. In: Calamoneri, T., Cor\u00f2, F. (eds.) Algorithms and Complexity - 12th International Conference, CIAC. Lecture Notes in Computer Science, vol. 12701, pp. 381\u2013393. Springer, Virtual event (2021). https:\/\/doi.org\/10.1007\/978-3-030-75242-2_27","DOI":"10.1007\/978-3-030-75242-2_27"},{"issue":"11","key":"10215_CR49","doi-asserted-by":"publisher","first-page":"1276","DOI":"10.1016\/j.ic.2008.07.005","volume":"206","author":"P Fraigniaud","year":"2008","unstructured":"Fraigniaud, P., Ilcinkas, D., Pelc, A.: Tree exploration with advice. Inf. Comput. 206(11), 1276\u20131287 (2008). https:\/\/doi.org\/10.1016\/j.ic.2008.07.005","journal-title":"Inf. Comput."},{"key":"10215_CR50","doi-asserted-by":"publisher","unstructured":"Dobrev, S., Kr\u00e1lovi\u010d, R., Markou, E.: Online graph exploration with advice. In: Even, G., Halld\u00f3rsson, M.M. (eds.) Structural Information and Communication Complexity - 19th International Colloquium, SIROCCO 2012, Reykjavik, Iceland, June 30-July 2, 2012, Revised Selected Papers. Lecture Notes in Computer Science, vol. 7355, pp. 267\u2013278. Springer, Berlin Heidelberg (2012). https:\/\/doi.org\/10.1007\/978-3-642-31104-8_23","DOI":"10.1007\/978-3-642-31104-8_23"},{"key":"10215_CR51","doi-asserted-by":"publisher","unstructured":"Gorain, B., Pelc, A.: Deterministic graph exploration with advice. ACM Trans. Algorithms 15(1), 8:1\u20138:17 (2019). https:\/\/doi.org\/10.1145\/3280823","DOI":"10.1145\/3280823"},{"key":"10215_CR52","doi-asserted-by":"publisher","unstructured":"B\u00f6ckenhauer, H.-J., Fuchs, J., Unger, W.: Exploring sparse graphs with advice. Inf. Comput. 289(Part), 104950 (2022). https:\/\/doi.org\/10.1016\/j.ic.2022.104950","DOI":"10.1016\/j.ic.2022.104950"},{"issue":"4","key":"10215_CR53","doi-asserted-by":"publisher","first-page":"593","DOI":"10.1007\/s00224-019-09955-7","volume":"64","author":"A Borodin","year":"2020","unstructured":"Borodin, A., Boyar, J., Larsen, K.S., Pankratov, D.: Advice complexity of priority algorithms. Theory Comput. Syst. 64(4), 593\u2013625 (2020). https:\/\/doi.org\/10.1007\/s00224-019-09955-7","journal-title":"Theory Comput. Syst."},{"key":"10215_CR54","doi-asserted-by":"publisher","DOI":"10.1016\/J.TCS.2023.114318","volume":"984","author":"J Boyar","year":"2024","unstructured":"Boyar, J., Larsen, K.S., Pankratov, D.: Advice complexity of adaptive priority algorithms. Theor. Comput. Sci. 984, 114318 (2024). https:\/\/doi.org\/10.1016\/J.TCS.2023.114318","journal-title":"Theor. Comput. Sci."},{"key":"10215_CR55","doi-asserted-by":"publisher","unstructured":"B\u00f6ckenhauer, H.-J., Frei, F., Horvath, S.: Priority algorithms with advice for disjoint path allocation problems (extended abstract). In: Hsieh, S.-Y., Hung, L.-J., Klasing, R., Lee, C.-W., Peng, S.-L. (eds.) New Trends in Computer Technologies and Applications - 25th International Computer Symposium, ICS. Communications in Computer and Information Science, vol. 1723, pp. 25\u201336. Springer, Taoyuan, Taiwan (2022). https:\/\/doi.org\/10.1007\/978-981-19-9582-8_3","DOI":"10.1007\/978-981-19-9582-8_3"},{"key":"10215_CR56","doi-asserted-by":"publisher","unstructured":"Angelopoulos, S., D\u00fcrr, C., Jin, S., Kamali, S., Renault, M.P.: Online computation with untrusted advice. In: Vidick, T. (ed.) 11th Innovations in Theoretical Computer Science Conference, ITCS. LIPIcs, vol. 151, pp. 52:1\u201352:15. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, Seattle, Washington (2020). https:\/\/doi.org\/10.4230\/LIPIcs.ITCS.2020.52","DOI":"10.4230\/LIPIcs.ITCS.2020.52"},{"key":"10215_CR57","doi-asserted-by":"publisher","unstructured":"Lee, R., Maghakian, J., Hajiesmaili, M.H., Li, J., Sitaraman, R.K., Liu, Z.: Online peak-aware energy scheduling with untrusted advice. In: Meer, H., Meo, M. (eds.) e-Energy \u201921: The Twelfth ACM International Conference on Future Energy Systems, pp. 107\u2013123. ACM, Torino, Italy (2021). https:\/\/doi.org\/10.1145\/3447555.3464860","DOI":"10.1145\/3447555.3464860"},{"key":"10215_CR58","doi-asserted-by":"publisher","unstructured":"Angelopoulos, S., Kamali, S.: R\u00e9nyi-ulam games and online computation with imperfect advice. In: Leroux, J., Lombardy, S., Peleg, D. (eds.) 48th International Symposium on Mathematical Foundations of Computer Science, MFCS 2023. LIPIcs, vol. 272, pp. 13:1\u201313:15. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, Dagstuhl, Germany (2023). https:\/\/doi.org\/10.4230\/LIPICS.MFCS.2023.13","DOI":"10.4230\/LIPICS.MFCS.2023.13"},{"key":"10215_CR59","unstructured":"Almanza, M., Chierichetti, F., Lattanzi, S., Panconesi, A., Re, G.: Online facility location with multiple advice. In: Ranzato, M., Beygelzimer, A., Dauphin, Y.N., Liang, P., Vaughan, J.W. (eds.) Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, NeurIPS 2021, December 6-14, 2021, Virtual, pp. 4661\u20134673 (2021). https:\/\/proceedings.neurips.cc\/paper\/2021\/hash\/250473494b245120a7eaf8b2e6b1f17c-Abstract.html"},{"key":"10215_CR60","doi-asserted-by":"publisher","unstructured":"Antoniadis, A., Gouleakis, T., Kleer, P., Kolev, P.: Secretary and online matching problems with machine learned advice. Discret. Optim. 48(Part 2), 100778 (2023). https:\/\/doi.org\/10.1016\/J.DISOPT.2023.100778","DOI":"10.1016\/J.DISOPT.2023.100778"},{"key":"10215_CR61","doi-asserted-by":"publisher","unstructured":"Rohatgi, D.: Near-optimal bounds for online caching with machine learned advice. In: Chawla, S. (ed.) Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, pp 1834\u20131845. SIAM, Salt Lake City, USA (2020). https:\/\/doi.org\/10.1137\/1.9781611975994.112","DOI":"10.1137\/1.9781611975994.112"},{"key":"10215_CR62","unstructured":"Wang, S., Li, J., Wang, S.: Online algorithms for multi-shop ski rental with machine learned advice. In: Larochelle, H., Ranzato, M., Hadsell, R., Balcan, M.-F., Lin, H.-T. (eds.) Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, Virtual (2020). https:\/\/proceedings.neurips.cc\/paper\/2020\/hash\/5cc4bb753030a3d804351b2dfec0d8b5-Abstract.html"},{"key":"10215_CR63","doi-asserted-by":"publisher","unstructured":"Kasilag, C.G.R., Rey, P.M., Clemente, J.B.: Solving the online assignment problem with machine learned advice. CoRR arXiv:2208.04016https:\/\/doi.org\/10.48550\/arXiv.2208.04016 (2022)","DOI":"10.48550\/arXiv.2208.04016"},{"key":"10215_CR64","unstructured":"Indyk, P., Mallmann-Trenn, F., Mitrovic, S., Rubinfeld, R.: Online page migration with ML advice. In: Camps-Valls, G., Ruiz, F.J.R., Valera, I. (eds.) International Conference on Artificial Intelligence and Statistics, AISTATS. Proceedings of Machine Learning Research, vol. 151, pp. 1655\u20131670. PMLR, Virtual event (2022). https:\/\/proceedings.mlr.press\/v151\/indyk22a.html"},{"key":"10215_CR65","doi-asserted-by":"publisher","unstructured":"Emek, Y., Gil, Y., Pacut, M., Schmid, S.: Online algorithms with randomly infused advice. CoRR arXiv:2302.05366https:\/\/doi.org\/10.48550\/arXiv.2302.05366 (2023)","DOI":"10.48550\/arXiv.2302.05366"},{"key":"10215_CR66","doi-asserted-by":"publisher","unstructured":"Frei, F.: Beneath, behind, and beyond common complexity classes. PhD thesis, ETH Zurich, Z\u00fcrich, Switzerland (2021). https:\/\/doi.org\/10.3929\/ethz-b-000542575","DOI":"10.3929\/ethz-b-000542575"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-025-10215-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00224-025-10215-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-025-10215-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,4,8]],"date-time":"2025-04-08T17:16:51Z","timestamp":1744132611000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00224-025-10215-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,3]]},"references-count":66,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2025,3]]}},"alternative-id":["10215"],"URL":"https:\/\/doi.org\/10.1007\/s00224-025-10215-0","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,3]]},"assertion":[{"value":"10 February 2025","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"1 March 2025","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare no Conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}],"article-number":"14"}}