{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T12:34:31Z","timestamp":1759667671841,"version":"3.37.3"},"reference-count":25,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2016,11,17]],"date-time":"2016-11-17T00:00:00Z","timestamp":1479340800000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/100007543","name":"Grantova Agentura, Univerzita Karlova","doi-asserted-by":"publisher","award":["548214"],"award-info":[{"award-number":["548214"]}],"id":[{"id":"10.13039\/100007543","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001824","name":"Czech Science Foundation (CZ)","doi-asserted-by":"publisher","award":["14-10003S"],"award-info":[{"award-number":["14-10003S"]}],"id":[{"id":"10.13039\/501100001824","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2018,1]]},"DOI":"10.1007\/s00453-016-0248-2","type":"journal-article","created":{"date-parts":[[2016,11,17]],"date-time":"2016-11-17T09:44:30Z","timestamp":1479375870000},"page":"155-184","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":8,"title":["Colored Bin Packing: Online Algorithms and Lower Bounds"],"prefix":"10.1007","volume":"80","author":[{"given":"Martin","family":"B\u00f6hm","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Gy\u00f6rgy","family":"D\u00f3sa","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Leah","family":"Epstein","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ji\u0159\u00ed","family":"Sgall","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pavel","family":"Vesel\u00fd","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2016,11,17]]},"reference":[{"key":"248_CR1","doi-asserted-by":"crossref","first-page":"238","DOI":"10.1016\/j.dam.2003.05.006","volume":"143","author":"L Babel","year":"2004","unstructured":"Babel, L., Chen, B., Kellerer, H., Kotov, V.: Algorithms for on-line bin-packing problems with cardinality constraints. Discrete Appl. Math. 143, 238\u2013251 (2004)","journal-title":"Discrete Appl. Math."},{"issue":"1","key":"248_CR2","doi-asserted-by":"crossref","first-page":"137","DOI":"10.1007\/s00224-014-9538-8","volume":"56","author":"J Balogh","year":"2015","unstructured":"Balogh, J., B\u00e9k\u00e9si, J., D\u00f3sa, G., Epstein, L., Kellerer, H., Tuza, Z.: Online results for black and white bin packing. Theory Comput. Syst. 56(1), 137\u2013155 (2015)","journal-title":"Theory Comput. Syst."},{"key":"248_CR3","doi-asserted-by":"crossref","unstructured":"Balogh, J., B\u00e9k\u00e9si, J., D\u00f3sa, G., Kellerer, H., Tuza, Z.: Black and white bin packing. In: Approximation and Online Algorithms. LNCS, vol. 7846, pp. 131\u2013144. Springer, Berlin (2013)","DOI":"10.1007\/978-3-642-38016-7_12"},{"key":"248_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."},{"key":"248_CR5","doi-asserted-by":"crossref","unstructured":"Balogh, J., B\u00e9k\u00e9si, J., D\u00f3sa, G., Sgall, J., van Stee, R.: The optimal absolute ratio for online bin packing. In: Proceedings of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp 1425\u20131438. ACM-SIAM (2015)","DOI":"10.1137\/1.9781611973730.94"},{"key":"248_CR6","doi-asserted-by":"crossref","unstructured":"B\u00f6hm, M., Sgall, J., Vesel\u00fd, P.: Online colored bin packing. In: Approximation and Online Algorithms. LNCS, vol. 8952, pp. 35\u201346. Springer, Berlin (2015)","DOI":"10.1007\/978-3-319-18263-6_4"},{"key":"248_CR7","doi-asserted-by":"crossref","unstructured":"Chrobak, M., Sgall, J., Woeginger, G.J.: Two-bounded-space bin packing revisited. In: European Symposium on Algorithms (ESA). LNCS, vol. 6942, pp. 263\u2013274. Springer, Berlin (2011)","DOI":"10.1007\/978-3-642-23719-5_23"},{"key":"248_CR8","doi-asserted-by":"crossref","first-page":"455","DOI":"10.1007\/978-1-4419-7997-1_35","volume-title":"Handbook of Combinatorial Optimization","author":"E Coffman\u00a0Jr","year":"2013","unstructured":"Coffman\u00a0Jr, E., 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, Berlin (2013)"},{"issue":"2","key":"248_CR9","doi-asserted-by":"crossref","first-page":"115","DOI":"10.1007\/s00453-001-0041-7","volume":"31","author":"J Csirik","year":"2001","unstructured":"Csirik, J., Johnson, D.S.: Bounded space on-line bin packing: best is better than first. Algorithmica 31(2), 115\u2013138 (2001)","journal-title":"Algorithmica"},{"key":"248_CR10","doi-asserted-by":"crossref","unstructured":"D\u00f3sa, G., Epstein, L.: Colorful bin packing. In: Algorithm Theory SWAT. LNCS, vol. 8503, pp. 170\u2013181. Springer, Berlin (2014)","DOI":"10.1007\/978-3-319-08404-6_15"},{"key":"248_CR11","unstructured":"D\u00f3sa, G., Epstein, L.: Online bin packing with cardinality constraints revisited. arXiv:1404.1056"},{"key":"248_CR12","unstructured":"D\u00f3sa, G., Sgall, J.: First Fit bin packing: A tight analysis. 30th International Symposium on Theoretical Aspects of Computer Science (STACS), Volume 20 of Leibniz International Proceedings in Informatics (LIPIcs), pp. 538\u2013549. Dagstuhl, Germany (2013)"},{"key":"248_CR13","doi-asserted-by":"crossref","unstructured":"D\u00f3sa, G., Sgall, J.: Optimal analysis of Best Fit bin packing. In: Automata, Languages, and Programming (ICALP). LNCS, vol. 8572, pp. 429\u2013441. Springer, Berlin (2014)","DOI":"10.1007\/978-3-662-43948-7_36"},{"issue":"3","key":"248_CR14","doi-asserted-by":"crossref","first-page":"416","DOI":"10.1007\/s10878-011-9408-0","volume":"26","author":"G D\u00f3sa","year":"2013","unstructured":"D\u00f3sa, G., Tuza, Z., Ye, D.: Bin packing with \u201clargest in bottom\u201d constraint: tighter bounds and generalizations. J. Comb. Optim. 26(3), 416\u2013436 (2013)","journal-title":"J. Comb. Optim."},{"key":"248_CR15","doi-asserted-by":"crossref","first-page":"1015","DOI":"10.1137\/050639065","volume":"20","author":"L Epstein","year":"2006","unstructured":"Epstein, L.: Online bin packing with cardinality constraints. SIAM J. Discrete Math. 20, 1015\u20131030 (2006)","journal-title":"SIAM J. Discrete Math."},{"issue":"8","key":"248_CR16","doi-asserted-by":"crossref","first-page":"780","DOI":"10.1002\/nav.20383","volume":"56","author":"L Epstein","year":"2009","unstructured":"Epstein, L.: On online bin packing with LIB constraints. Naval Res. Logist. 56(8), 780\u2013786 (2009)","journal-title":"Naval Res. Logist."},{"issue":"3","key":"248_CR17","doi-asserted-by":"crossref","first-page":"163","DOI":"10.1051\/ro:2006001","volume":"39","author":"L Finlay","year":"2005","unstructured":"Finlay, L., Manyem, P.: Online LIB problems: heuristics for bin covering and lower bounds for bin packing. RAIRO Oper. Res. 39(3), 163\u2013183 (2005)","journal-title":"RAIRO Oper. Res."},{"key":"248_CR18","doi-asserted-by":"crossref","unstructured":"Fujiwara, H., Kobayashi, K.: Improved lower bounds for the online bin packing problem with cardinality constraints. In: Computing and Combinatorics, LNCS, vol. 7936, pp. 518\u2013530. Springer, Berlin (2013)","DOI":"10.1007\/978-3-642-38768-5_46"},{"key":"248_CR19","unstructured":"Johnson, D.: Near-Optimal Bin Packing Algorithms. Massachusetts Institute of Technology, Project MAC. Massachusetts Institute of Technology (1973)"},{"key":"248_CR20","doi-asserted-by":"crossref","first-page":"522","DOI":"10.1145\/321906.321917","volume":"22","author":"KL Krause","year":"1975","unstructured":"Krause, K.L., Shen, V.Y., Schwetman, H.D.: Analysis of several task-scheduling algorithms for a model of multiprogramming computer systems. J. ACM 22, 522\u2013550 (1975)","journal-title":"J. ACM"},{"key":"248_CR21","doi-asserted-by":"crossref","first-page":"562","DOI":"10.1145\/3828.3833","volume":"32","author":"CC Lee","year":"1985","unstructured":"Lee, C.C., Lee, D.T.: A simple on-line bin-packing algorithm. J. ACM 32, 562\u2013572 (1985)","journal-title":"J. ACM"},{"issue":"E","key":"248_CR22","doi-asserted-by":"crossref","first-page":"E186","DOI":"10.21914\/anziamj.v43i0.470","volume":"43","author":"P Manyem","year":"2002","unstructured":"Manyem, P.: Bin packing and covering with longest items at the bottom: online version. ANZIAM J. 43(E), E186\u2013E232 (2002)","journal-title":"ANZIAM J."},{"issue":"4","key":"248_CR23","first-page":"663","volume":"8","author":"P Manyem","year":"2003","unstructured":"Manyem, P., Salt, R.L., Visser, M.S.: Approximation lower bounds in online LIB bin packing and covering. J. Automata Lang. Comb. 8(4), 663\u2013674 (2003)","journal-title":"J. Automata Lang. Comb."},{"key":"248_CR24","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":"248_CR25","unstructured":"Ullman, J.: The Performance of a Memory Allocation Algorithm. Technical Report 100 (1971)"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-016-0248-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-016-0248-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-016-0248-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,9,15]],"date-time":"2019-09-15T14:18:06Z","timestamp":1568557086000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-016-0248-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,11,17]]},"references-count":25,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2018,1]]}},"alternative-id":["248"],"URL":"https:\/\/doi.org\/10.1007\/s00453-016-0248-2","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2016,11,17]]}}}