{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,16]],"date-time":"2026-03-16T23:01:14Z","timestamp":1773702074016,"version":"3.50.1"},"reference-count":31,"publisher":"Springer Science and Business Media LLC","issue":"8","license":[{"start":{"date-parts":[[2018,4,12]],"date-time":"2018-04-12T00:00:00Z","timestamp":1523491200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100001665","name":"Agence Nationale de la Recherche","doi-asserted-by":"publisher","award":["ANR-11-BS02-0015"],"award-info":[{"award-number":["ANR-11-BS02-0015"]}],"id":[{"id":"10.13039\/501100001665","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2018,11]]},"DOI":"10.1007\/s00224-018-9862-5","type":"journal-article","created":{"date-parts":[[2018,4,12]],"date-time":"2018-04-12T05:35:37Z","timestamp":1523511337000},"page":"2006-2034","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":10,"title":["Online Bin Packing with Advice of Small Size"],"prefix":"10.1007","volume":"62","author":[{"given":"Spyros","family":"Angelopoulos","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Christoph","family":"D\u00fcrr","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Shahin","family":"Kamali","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Marc P.","family":"Renault","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Adi","family":"Ros\u00e9n","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2018,4,12]]},"reference":[{"key":"9862_CR1","doi-asserted-by":"crossref","unstructured":"Adamaszek, A., Renault, M.P., Ros\u0117n, A., van Stee, R.: Reordering buffer management with advice. J. Schedul. (2016)","DOI":"10.1007\/s10951-016-0487-8"},{"key":"9862_CR2","doi-asserted-by":"crossref","unstructured":"Angelopoulos, S., D\u00fcrr, C., Kamali, S., Renault, M.P., Ros\u00e9n, A.: Online bin packing with advice of small size. In: Dehne, F., Sack, J., Stege, U. (eds.) Algorithms and Data Structures - 14th International Symposium, WADS 2015, Victoria, BC, Canada, August 5-7, 2015. Proceedings, Lecture Notes in Computer Science, vol. 9214, pp 40\u201353. Springer (2015)","DOI":"10.1007\/978-3-319-21840-3_4"},{"issue":"3","key":"9862_CR3","first-page":"361","volume":"15","author":"E Asgeirsson","year":"2002","unstructured":"Asgeirsson, E., Ayesta, U., Coffman, E., Etra, J., Momcilovic, P., Phillips, D., Vokhshoori, V., Wang, Z., Wolfe, J.: Closed on-line bin packing. Acta Cybernet. 15(3), 361\u2013367 (2002)","journal-title":"Acta Cybernet."},{"key":"9862_CR4","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.tcs.2012.04.017","volume":"440\u2013441","author":"J Balogh","year":"2012","unstructured":"Balogh, J., B\u00e9k\u00e9si, J., Galambos, G.: New lower bounds for certain classes of bin packing algorithms. Theoret. Comput. Sci. 440\u2013441, 1\u201313 (2012)","journal-title":"Theoret. Comput. Sci."},{"key":"9862_CR5","doi-asserted-by":"crossref","unstructured":"Bianchi, M.P., B\u00f6ckenhauer, H., Br\u00fclisauer, T., Komm, D., Palano, B.: Online minimum spanning tree with advice - (extended abstract). In: Freivalds, R.M., Engels, G., Catania, B. (eds.) SOFSEM 2016: Theory and Practice of Computer Science - 42nd International Conference on Current Trends in Theory and Practice of Computer Science, Harrachov, Czech Republic, January 23-28, 2016, Proceedings, Lecture Notes in Computer Science, vol. 9587, pp 195\u2013207. Springer (2016)","DOI":"10.1007\/978-3-662-49192-8_16"},{"key":"9862_CR6","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1016\/j.tcs.2014.01.027","volume":"527","author":"H Bo\u0307ckenhauer","year":"2014","unstructured":"Bo\u0307ckenhauer, H., Komm, D., Kra\u0307lovic, R., Rossmanith, P.: The online knapsack problem: Advice and randomization. Theor. Comput. Sci. 527, 61\u201372 (2014)","journal-title":"Theor. Comput. Sci."},{"key":"9862_CR7","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1016\/j.tcs.2014.06.006","volume":"554","author":"HJ B\u00f6ckenhauer","year":"2014","unstructured":"B\u00f6ckenhauer, H.J., Hromkovic, J., Komm, D., Krug, S., Smula, J., Sprock, A.: The string guessing problem as a method to prove lower bounds on the advice complexity. Theoret. Comput. Sci. 554, 95\u2013108 (2014)","journal-title":"Theoret. Comput. Sci."},{"key":"9862_CR8","doi-asserted-by":"crossref","unstructured":"B\u00f6ckenhauer, H.J., Komm, D., Kr\u00e1lovi\u010d, R., Kr\u00e1lovi\u010d, R.: On the advice complexity of the k-server problem. In: Proc. 38th International Colloquium on Automata, Languages, and Programming (ICALP), Lecture Notes in Comput. Sci., vol. 6755, pp. 207\u2013218. Springer (2011)","DOI":"10.1007\/978-3-642-22006-7_18"},{"key":"9862_CR9","doi-asserted-by":"crossref","unstructured":"B\u00f6ckenhauer, H.J., Komm, D., Kr\u00e1lovi\u010d, R., Kr\u00e1lovi\u010d, R., M\u00f6mke, T.: On the advice complexity of online problems. In: Proc. 20th International Symp. on Algorithms and Computation (ISAAC), Lecture Notes in Comput. Sci., vol. 5878, pp. 331\u2013340. Springer (2009)","DOI":"10.1007\/978-3-642-10631-6_35"},{"key":"9862_CR10","unstructured":"Borodin, A., El-Yaniv, R.: Online Computation and Competitive Analysis. Cambridge University Press (1998)"},{"issue":"3","key":"9862_CR11","doi-asserted-by":"publisher","first-page":"93","DOI":"10.1145\/2993749.2993766","volume":"47","author":"J Boyar","year":"2016","unstructured":"Boyar, J., Favrholdt, L., Kudahl, C., Larsen, K. S., Mikkelsen, J.W.: Online algorithms with advice: A survey. SIGACT News 47(3), 93\u2013129 (2016)","journal-title":"SIGACT News"},{"key":"9862_CR12","doi-asserted-by":"crossref","unstructured":"Boyar, J., Kamali, S., Larsen, K.S., L\u00f3pez-Ortiz, A.: On the list update problem with advice. Inf. Comput. (2016)","DOI":"10.1016\/j.ic.2016.06.007"},{"issue":"1","key":"9862_CR13","doi-asserted-by":"publisher","first-page":"507","DOI":"10.1007\/s00453-014-9955-8","volume":"74","author":"J Boyar","year":"2016","unstructured":"Boyar, J., Kamali, S., Larsen, K.S., Lo\u0307pez-Ortiz, A.: Online bin packing with advice. Algorithmica 74(1), 507\u2013527 (2016)","journal-title":"Algorithmica"},{"key":"9862_CR14","doi-asserted-by":"crossref","unstructured":"Dobrev, S., Kralovic, R., Pardubsk\u00e1, D.: How much information about the future is needed? In: Proc. 34th International Conf. on Current Trends in Theory and Practice of Computer Science (SOFSEM), Lecture Notes in Comput. Sci., vol. 4910, pp. 247\u2013258. Springer (2008)","DOI":"10.1007\/978-3-540-77566-9_21"},{"issue":"3","key":"9862_CR15","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 Inform Theor. Appl. 43(3), 585\u2013613 (2009)","journal-title":"RAIRO Inform Theor. Appl."},{"issue":"24","key":"9862_CR16","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. Theoret. Comput. Sci. 412(24), 2642\u20132656 (2011)","journal-title":"Theoret. Comput. Sci."},{"issue":"3","key":"9862_CR17","doi-asserted-by":"publisher","first-page":"1270","DOI":"10.1137\/060666329","volume":"19","author":"L Epstein","year":"2008","unstructured":"Epstein, L., Levin, A.: On bin packing with conflicts. SIAM J. Optim. 19 (3), 1270\u20131298 (2008)","journal-title":"SIAM J. Optim."},{"key":"9862_CR18","doi-asserted-by":"publisher","first-page":"329","DOI":"10.1007\/BF02248693","volume":"49","author":"G Galambos","year":"1993","unstructured":"Galambos, G., Woeginger, G.J.: Repacking helps in bounded space online bin packing. Computing 49, 329\u2013338 (1993)","journal-title":"Computing"},{"issue":"5","key":"9862_CR19","doi-asserted-by":"publisher","first-page":"1532","DOI":"10.1137\/S0097539799180408","volume":"30","author":"G Gambosi","year":"2000","unstructured":"Gambosi, G., Postiglione, A., Talamo, M.: Algorithms for the relaxed online bin-packing model. SIAM J. Comput. 30(5), 1532\u20131551 (2000)","journal-title":"SIAM J. Comput."},{"key":"9862_CR20","doi-asserted-by":"crossref","unstructured":"Garey, M.R., Graham, R.L., Ullman, J.D.: Worst-case analysis of memory allocation algorithms. In: Fischer, P.C., Zeiger, H.P., Ullman, J.D., Rosenberg, A.L. (eds.) STOC, pp 143\u2013150. ACM (1972)","DOI":"10.1145\/800152.804907"},{"key":"9862_CR21","doi-asserted-by":"crossref","unstructured":"Garey, M.R., Johnson, D.S.: Approximation algorithms for bin packing problems - a survey. In: Ausiello, G., Lucertini, M. (eds.) Analysis and Design of Algorithms in Combinatorial Optimization, pp 147\u2013172. Springer, New York (1981)","DOI":"10.1007\/978-3-7091-2748-3_8"},{"key":"9862_CR22","unstructured":"Grove, E.F.: Online binpacking with lookahead. In: Proc. 6th Symp. on Discrete Algorithms (SODA), pp. 430\u2013436 (1995)"},{"issue":"3","key":"9862_CR23","doi-asserted-by":"publisher","first-page":"476","DOI":"10.1007\/s00224-015-9649-x","volume":"59","author":"S Gupta","year":"2016","unstructured":"Gupta, S., Kamali, S., L\u00f3pez-Ortiz, A.: On advice complexity of the k-server problem under sparse metrics. Theory Comput. Syst. 59(3), 476\u2013499 (2016)","journal-title":"Theory Comput. Syst."},{"key":"9862_CR24","unstructured":"Heydrich, S., van Stee, R.: Beating the harmonic lower bound for online bin packing. In: 43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016, July 11-15, 2016, Rome, Italy, pp. 41:1\u201341:14 (2016)"},{"key":"9862_CR25","unstructured":"Johnson, D.S.: Near-Optimal Bin Packing Algorithms. Ph.D. thesis, MIT, Cambridge MA (1973)"},{"key":"9862_CR26","doi-asserted-by":"publisher","first-page":"256","DOI":"10.1137\/0203025","volume":"3","author":"DS Johnson","year":"1974","unstructured":"Johnson, D.S., Demers, A., Ullman, J.D., Garey, M.R., Graham, R.L.: Worst-case performance bounds for simple one-dimensional packing algorithms. SIAM J. Comput. 3, 256\u2013278 (1974)","journal-title":"SIAM J. Comput."},{"key":"9862_CR27","unstructured":"M., J.W.: Randomization can be as helpful as a glimpse of the future in online computation. In: 43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016, July 11-15, 2016, Rome, Italy, pp. 39:1\u201339:14 (2016)"},{"issue":"2","key":"9862_CR28","doi-asserted-by":"publisher","first-page":"249","DOI":"10.1051\/ita\/2011105","volume":"45","author":"D Komm","year":"2011","unstructured":"Komm, D., Kr\u00e1lovi\u010d, R.: Advice complexity and barely random algorithms. RAIRO Inform Theor. Appl. 45(2), 249\u2013267 (2011)","journal-title":"RAIRO Inform Theor. Appl."},{"issue":"1","key":"9862_CR29","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1007\/s00224-012-9434-z","volume":"56","author":"MP Renault","year":"2015","unstructured":"Renault, M.P., Ros\u0117n, A.: On online algorithms with advice for the k-server problem. Theory Comput. Syst. 56(1), 3\u201321 (2015)","journal-title":"Theory Comput. Syst."},{"key":"9862_CR30","doi-asserted-by":"publisher","first-page":"155","DOI":"10.1016\/j.tcs.2015.07.050","volume":"600","author":"MP Renault","year":"2015","unstructured":"Renault, M.P., Ros\u0117n, A., van Stee, R.: Online algorithms with advice for bin packing and scheduling problems. Theor. Comput. Sci. 600, 155\u2013170 (2015)","journal-title":"Theor. Comput. Sci."},{"key":"9862_CR31","unstructured":"Sloane, N.J.A.: The on-line encyclopedia of integer sequences. Sequence A000041"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-018-9862-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-018-9862-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-018-9862-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,8,19]],"date-time":"2022-08-19T02:27:44Z","timestamp":1660876064000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-018-9862-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,4,12]]},"references-count":31,"journal-issue":{"issue":"8","published-print":{"date-parts":[[2018,11]]}},"alternative-id":["9862"],"URL":"https:\/\/doi.org\/10.1007\/s00224-018-9862-5","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,4,12]]},"assertion":[{"value":"12 April 2018","order":1,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}