{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,12]],"date-time":"2026-02-12T15:15:53Z","timestamp":1770909353240,"version":"3.50.1"},"reference-count":36,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2014,11,7]],"date-time":"2014-11-07T00:00:00Z","timestamp":1415318400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2016,1]]},"DOI":"10.1007\/s00453-014-9955-8","type":"journal-article","created":{"date-parts":[[2014,11,14]],"date-time":"2014-11-14T12:39:09Z","timestamp":1415968749000},"page":"507-527","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":31,"title":["Online Bin Packing with Advice"],"prefix":"10.1007","volume":"74","author":[{"given":"Joan","family":"Boyar","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Shahin","family":"Kamali","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kim S.","family":"Larsen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Alejandro","family":"L\u00f3pez-Ortiz","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2014,11,7]]},"reference":[{"key":"9955_CR1","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.tcs.2012.03.031","volume":"443","author":"S Albers","year":"2012","unstructured":"Albers, S., Hellwig, M.: Semi-online scheduling revisited. Theor. Comput. Sci. 443, 1\u20139 (2012)","journal-title":"Theor. Comput. Sci."},{"issue":"3","key":"9955_CR2","first-page":"361","volume":"15","author":"EI \u00c1sgeirsson","year":"2002","unstructured":"\u00c1sgeirsson, E.I., Ayesta, U., Coffman, E.G., Etra, J., Momcilovic, P., Phillips, D.J., Vokhshoori, V., Wang, Z., Wolfe, J.: Closed on-line bin packing. Acta Cybern. 15(3), 361\u2013367 (2002)","journal-title":"Acta Cybern."},{"issue":"4","key":"9955_CR3","doi-asserted-by":"crossref","first-page":"685","DOI":"10.1007\/s10100-012-0266-3","volume":"21","author":"J Balogh","year":"2013","unstructured":"Balogh, J., B\u00e9k\u00e9si, J.: Semi-on-line bin packing: a short overview and a new lower bound. Cent. Eur. J. Oper. Res. 21(4), 685\u2013698 (2013)","journal-title":"Cent. Eur. J. Oper. Res."},{"key":"9955_CR4","doi-asserted-by":"crossref","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. Theor. Comput. Sci. 440\u2013441, 1\u201313 (2012)","journal-title":"Theor. Comput. Sci."},{"issue":"1","key":"9955_CR5","doi-asserted-by":"crossref","first-page":"92","DOI":"10.1007\/s00453-013-9819-7","volume":"70","author":"MP Bianchi","year":"2014","unstructured":"Bianchi, M.P., B\u00f6ckenhauer, H., Hromkovic, J., Keller, L.: Online coloring of bipartite graphs with and without advice. Algorithmica 70(1), 92\u2013111 (2014)","journal-title":"Algorithmica"},{"key":"9955_CR6","doi-asserted-by":"crossref","unstructured":"Bianchi, M.P., B\u00f6ckenhauer, H.J., Hromkovic, J., Keller, L.: Online coloring of bipartite graphs with and without advice. In: Gudmundsson, J., Mestre, J., Viglas, T. (eds.) Proc. 18th Computing and Combinatorics Conference (COCOON), Lecture Notes in Computer Science, vol. 7434, pp. 519\u2013530. Springer, Berlin (2012)","DOI":"10.1007\/978-3-642-32241-9_44"},{"key":"9955_CR7","doi-asserted-by":"crossref","unstructured":"Bianchi, M.P., B\u00f6ckenhauer, H.J., Hromkovic, J., Krug, S., Steffen, B.: On the advice complexity of the online $$L(2, 1)$$ L ( 2 , 1 ) -coloring problem on paths and cycles. In: Du, D., Zhang G. (eds.) Proc. 19th Computing and Combinatorics Conference (COCOON), Lecture Notes in Computer Science, vol. 7936, pp. 53\u201364. Springer, Berlin (2013)","DOI":"10.1007\/978-3-642-38768-5_7"},{"issue":"2","key":"9955_CR8","doi-asserted-by":"crossref","first-page":"80","DOI":"10.1016\/0167-6377(83)90042-1","volume":"2","author":"J B\u0142a\u017cewicz","year":"1983","unstructured":"B\u0142a\u017cewicz, J., Ecker, K.: A linear time algorithm for restricted bin packing and scheduling problems. Oper. Res. Lett. 2(2), 80\u201383 (1983)","journal-title":"Oper. Res. Lett."},{"key":"9955_CR9","doi-asserted-by":"crossref","first-page":"61","DOI":"10.1016\/j.tcs.2014.01.027","volume":"527","author":"H B\u00f6ckenhauer","year":"2014","unstructured":"B\u00f6ckenhauer, H., Komm, D., Kr\u00e1lovic, R., Rossmanith, P.: The online knapsack problem: advice and randomization. Theor. Comput. Sci. 527, 61\u201372 (2014)","journal-title":"Theor. Comput. Sci."},{"key":"9955_CR10","doi-asserted-by":"crossref","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. In: Du, D., Zhang, G. (eds.) Proc. 19th Computing and Combinatorics Conference (COCOON), Lecture Notes in Computer Science, vol. 7936, pp. 493\u2013505. Springer, Berlin (2013)","DOI":"10.1007\/978-3-642-38768-5_44"},{"key":"9955_CR11","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$$ k -server problem. In: Aceto, L., Henzinger, M., Sgall, J. (eds.) Proc. 38th International Colloquium on Automata, Languages, and Programming (ICALP), Lecture Notes in Computer Science, vol. 6755, pp. 207\u2013218. Springer, Berlin (2011)","DOI":"10.1007\/978-3-642-22006-7_18"},{"key":"9955_CR12","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: Dong, Y., Du, D., Ibarra, O.H. (eds.) Proc. 20th International Symposium on Algorithms and Computation (ISAAC), Lecture Notes in Computer Science, vol. 5878, pp. 331\u2013340. Springer, Berlin (2009)","DOI":"10.1007\/978-3-642-10631-6_35"},{"key":"9955_CR13","doi-asserted-by":"crossref","unstructured":"Boyar, J., Kamali, S., Larsen, K.S., L\u00f3pez-Ortiz, A.: On the list update problem with advice. In: Dediu, A.H., Mart\u00edn-Vide, C., Sierra-Rodr\u00edguez, J.L., Truthe, B. (eds.) Proc. 8th International Conference on Language and Automata Theory and Applications (LATA), pp. 210\u2013221 (2014)","DOI":"10.1007\/978-3-319-04921-2_17"},{"issue":"1\u20133","key":"9955_CR14","doi-asserted-by":"crossref","first-page":"134","DOI":"10.1016\/j.tcs.2004.11.018","volume":"337","author":"TCE Cheng","year":"2005","unstructured":"Cheng, T.C.E., Kellerer, H., Kotov, V.: Semi-on-line multiprocessor scheduling with given total processing time. Theor. Comput. Sci. 337(1\u20133), 134\u2013146 (2005)","journal-title":"Theor. Comput. Sci."},{"key":"9955_CR15","volume-title":"Approximation Algorithms for NP-Hard Problems","author":"EG Coffman","year":"1997","unstructured":"Coffman, E.G., Garey, M.R., Johnson, D.S.: Approximation algorithms for bin packing: a survey. In: Hochbaum, D. (ed.) Approximation Algorithms for NP-Hard Problems. PWS Publishing Co, Boston (1997)"},{"key":"9955_CR16","doi-asserted-by":"crossref","first-page":"455","DOI":"10.1007\/978-1-4419-7997-1_35","volume-title":"Handbook of Combinatorial Optimization","author":"EG Coffman Jr","year":"2013","unstructured":"Coffman Jr, E.G., Csirik, J., Galambos, G., Martello, S., Vigo, D.: Bin packing approximation algorithms: survey and classification. In: Pardalos, P.M., Du, D.Z., Graham, R.L. (eds.) Handbook of Combinatorial Optimization, pp. 455\u2013531. Springer, New York (2013)"},{"key":"9955_CR17","doi-asserted-by":"crossref","first-page":"349","DOI":"10.1007\/BF02579456","volume":"1","author":"WF Vega de la","year":"1981","unstructured":"de la Vega, W.F., Lueker, G.S.: Bin packing can be solved within 1 + $$\\epsilon $$ \u03f5 in linear time. Combinatorica 1, 349\u2013355 (1981)","journal-title":"Combinatorica"},{"key":"9955_CR18","doi-asserted-by":"crossref","unstructured":"Dobrev, S., Kr\u00e1lovic, R., Markou, E.: Online graph exploration with advice. In: Even, G., Halld\u00f3rsson, M.M. (eds.) Proc. 19th International Colloquium on Structural Information and Communication Complexity (SIROCCO), Lecture Notes in Computer Science, vol. 7355, pp. 267\u2013278. Springer, Berlin (2012)","DOI":"10.1007\/978-3-642-31104-8_23"},{"issue":"3","key":"9955_CR19","doi-asserted-by":"crossref","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. Inform. Appl. 43(3), 585\u2013613 (2009)","journal-title":"RAIRO Theor. Inform. Appl."},{"issue":"24","key":"9955_CR20","doi-asserted-by":"crossref","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. Theor. Comput. Sci. 412(24), 2642\u20132656 (2011)","journal-title":"Theor. Comput. Sci."},{"issue":"3","key":"9955_CR21","doi-asserted-by":"crossref","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":"9955_CR22","doi-asserted-by":"crossref","unstructured":"Fori\u0161ek, M., Keller, L., Steinov\u00e1, M.: Advice complexity of online coloring for paths. In: Dediu, A.H., Mart\u00edn-Vide, C. (eds.) Proc. 6th International Conference on Language and Automata Theory and Applications (LATA), Lecture Notes in Computer Science, vol. 7183, pp. 228\u2013239. Springer, Berlin (2012)","DOI":"10.1007\/978-3-642-28332-1_20"},{"key":"9955_CR23","doi-asserted-by":"crossref","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":"9955_CR24","doi-asserted-by":"crossref","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":"9955_CR25","doi-asserted-by":"crossref","unstructured":"Goemans, M.X., Rothvo\u00df, T.: Polynomiality for bin packing with a constant number of item types. In: Chekuri, C. (ed.) Proc. 25th Symposium on Discrete Algorithms (SODA), pp. 830\u2013839 (2014)","DOI":"10.1137\/1.9781611973402.61"},{"key":"9955_CR26","unstructured":"Grove, E.F.: Online binpacking with lookahead. In: Clarkson, K.L. (ed.) Proc. 6th Symposium on Discrete Algorithms (SODA), pp. 430\u2013436 (1995)"},{"key":"9955_CR27","doi-asserted-by":"crossref","unstructured":"Hromkovi\u010d, J., Kr\u00e1lovi\u010d, R., Kr\u00e1lovi\u010d, R.: Information complexity of online problems. In: Hlinen\u00fd, P., Kucera, A. (eds.) Proc. 35th Symposium on Mathematical Foundations of Computer Science (MFCS), Lecture Notes in Computer Science, vol. 6281, pp. 24\u201336. Springer, Berlin (2010)","DOI":"10.1007\/978-3-642-15155-2_3"},{"key":"9955_CR28","doi-asserted-by":"crossref","first-page":"229","DOI":"10.1016\/0020-0190(96)00112-3","volume":"59","author":"Z Ivkovic","year":"1996","unstructured":"Ivkovic, Z., Lloyd, E.: A fundamental restriction on fully dynamic maintenance of bin packing. Inf. Process. Lett. 59, 229\u2013232 (1996)","journal-title":"Inf. Process. Lett."},{"key":"9955_CR29","doi-asserted-by":"crossref","unstructured":"Komm, D., Kr\u00e1lovic, R., M\u00f6mke, T.: On the advice complexity of the set cover problem. In: Hirsch, E.A., Karhum\u00e4ki, J., Lepist\u00f6, A., Prilutskii, M. (eds.) Proc. 7th International Computer Science Symposium in Russia (CSR), Lecture Notes in Computer Science, vol. 7353, pp. 241\u2013252. Springer, Berlin (2012)","DOI":"10.1007\/978-3-642-30642-6_23"},{"issue":"2","key":"9955_CR30","doi-asserted-by":"crossref","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 Theor. Inform. Appl. 45(2), 249\u2013267 (2011)","journal-title":"RAIRO Theor. Inform. Appl."},{"key":"9955_CR31","doi-asserted-by":"crossref","unstructured":"Renault, M.P., Ros\u00e9n, A.: On online algorithms with advice for the $$k$$ k -server problem. In: Solis-Oba, R., Persiano, G. (eds.) Proc. 9th International Workshop in Approximation and Online Algorithms (WAOA), Lecture Notes in Computer Science, vol. 7164, pp. 198\u2013210. Springer, Berlin (2011)","DOI":"10.1007\/978-3-642-29116-6_17"},{"key":"9955_CR32","unstructured":"Renault, M.P., Ros\u00e9n, A., van Stee, R.: Online algorithms with advice for bin packing and scheduling problems. CoRR abs\/1311.7589 (2013)"},{"key":"9955_CR33","doi-asserted-by":"crossref","unstructured":"Seibert, S., Sprock, A., Unger, W.: Advice complexity of the online coloring problem. In: Spirakis, P.G., Serna, M.J. (eds.) Proc. 8th International Conference on Algorithms and Complexity (CIAC), Lecture Notes in Computer Science, vol. 7878, pp. 345\u2013357. Springer, Berlin (2013)","DOI":"10.1007\/978-3-642-38233-8_29"},{"key":"9955_CR34","doi-asserted-by":"crossref","first-page":"640","DOI":"10.1145\/585265.585269","volume":"49","author":"SS Seiden","year":"2002","unstructured":"Seiden, S.S.: On the online bin packing problem. J. ACM 49, 640\u2013671 (2002)","journal-title":"J. ACM"},{"key":"9955_CR35","doi-asserted-by":"crossref","first-page":"2191","DOI":"10.1007\/978-1-4419-7997-1_2","volume-title":"Handbook of Combinatorial Optimization","author":"Z Tan","year":"2013","unstructured":"Tan, Z., Zhang, A.: Online and semi-online scheduling. In: Pardalos, P.M. (ed.) Handbook of Combinatorial Optimization, pp. 2191\u20132252. Springer, Berlin (2013)"},{"key":"9955_CR36","volume-title":"Approximation Algorithms","author":"VV Vazirani","year":"2004","unstructured":"Vazirani, V.V.: Approximation Algorithms. Springer, Berlin (2004)"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-014-9955-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-014-9955-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-014-9955-8","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,13]],"date-time":"2025-05-13T18:00:37Z","timestamp":1747159237000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-014-9955-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,11,7]]},"references-count":36,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2016,1]]}},"alternative-id":["9955"],"URL":"https:\/\/doi.org\/10.1007\/s00453-014-9955-8","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,11,7]]}}}