{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,3]],"date-time":"2026-05-03T17:04:48Z","timestamp":1777827888165,"version":"3.51.4"},"reference-count":45,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2025,8,4]],"date-time":"2025-08-04T00:00:00Z","timestamp":1754265600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2025,8,4]],"date-time":"2025-08-04T00:00:00Z","timestamp":1754265600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"publisher","award":["1467\/22"],"award-info":[{"award-number":["1467\/22"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Sched"],"published-print":{"date-parts":[[2026,2]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>\n                    We study two semi-online models for bin packing and exhibit them on cardinality constrained bin packing with small values of\n                    <jats:italic>k<\/jats:italic>\n                    . In this variant of the bin packing problem, each bin can have at most\n                    <jats:italic>k<\/jats:italic>\n                    items whose total size does not exceed 1. For the semi-online model where the algorithm may use a reordering buffer, we show that even if a single item can be stored in the buffer at any point in time, the best possible asymptotic competitive ratio for the case\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:tex-math>$$k=2$$<\/jats:tex-math>\n                        <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <mml:mrow>\n                            <mml:mi>k<\/mml:mi>\n                            <mml:mo>=<\/mml:mo>\n                            <mml:mn>2<\/mml:mn>\n                          <\/mml:mrow>\n                        <\/mml:math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    is smaller than that of the purely online problem. For the model with two parallel solutions, which is equivalent to the model with advice with a single bit of advice, we show an improved upper bound on the asymptotic competitive ratio for\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:tex-math>$$k=3$$<\/jats:tex-math>\n                        <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <mml:mrow>\n                            <mml:mi>k<\/mml:mi>\n                            <mml:mo>=<\/mml:mo>\n                            <mml:mn>3<\/mml:mn>\n                          <\/mml:mrow>\n                        <\/mml:math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    .\n                  <\/jats:p>","DOI":"10.1007\/s10951-025-00854-z","type":"journal-article","created":{"date-parts":[[2025,8,4]],"date-time":"2025-08-04T16:46:44Z","timestamp":1754326004000},"page":"51-66","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Semi-online models for cardinality constrained bin packing"],"prefix":"10.1007","volume":"29","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-6761-8521","authenticated-orcid":false,"given":"Leah","family":"Epstein","sequence":"first","affiliation":[]},{"given":"Asaf","family":"Levin","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2025,8,4]]},"reference":[{"key":"854_CR1","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.tcs.2012.03.031","volume":"443","author":"S Albers","year":"2012","unstructured":"Albers, S., & Hellwig, M. (2012). Semi-online scheduling revisited. Theoretical Computer Science, 443, 1\u20139.","journal-title":"Theoretical Computer Science"},{"issue":"2","key":"854_CR2","doi-asserted-by":"publisher","first-page":"492","DOI":"10.1007\/s00453-016-0172-5","volume":"78","author":"S Albers","year":"2017","unstructured":"Albers, S., & Hellwig, M. (2017). Online makespan minimization with parallel schedules. Algorithmica, 78(2), 492\u2013520.","journal-title":"Algorithmica"},{"issue":"8","key":"854_CR3","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. (2018). Online bin packing with advice of small size. Theory of Computing Systems, 62(8), 2006\u20132034.","journal-title":"Theory of Computing Systems"},{"issue":"1\u20133","key":"854_CR4","doi-asserted-by":"publisher","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. (2004). Algorithms for on-line bin-packing problems with cardinality constraints. Discrete Applied Mathematics, 143(1\u20133), 238\u2013251.","journal-title":"Discrete Applied Mathematics"},{"key":"854_CR5","unstructured":"Balogh, J., B\u00e9k\u00e9si, J., D\u00f3sa, G., Epstein, L., & Levin, A. (2018). A new and improved algorithm for online bin packing. In Proceeding of the 26th European symposium on algorithms (ESA2018) (pp. 5:1\u20135:14)."},{"issue":"8","key":"854_CR6","doi-asserted-by":"publisher","first-page":"1757","DOI":"10.1007\/s00224-019-09915-1","volume":"63","author":"J Balogh","year":"2019","unstructured":"Balogh, J., B\u00e9k\u00e9si, J., D\u00f3sa, G., Epstein, L., & Levin, A. (2019). Lower bounds for several online variants of bin packing. Theory of Computing Systems, 63(8), 1757\u20131780.","journal-title":"Theory of Computing Systems"},{"key":"854_CR7","doi-asserted-by":"publisher","first-page":"34","DOI":"10.1016\/j.jcss.2020.03.002","volume":"112","author":"J Balogh","year":"2020","unstructured":"Balogh, J., B\u00e9k\u00e9si, J., D\u00f3sa, G., Epstein, L., & Levin, A. (2020). Online bin packing with cardinality constraints resolved. Journal of Computer and System Sciences, 112, 34\u201349.","journal-title":"Journal of Computer and System Sciences"},{"issue":"7","key":"854_CR8","doi-asserted-by":"publisher","first-page":"2047","DOI":"10.1007\/s00453-021-00818-7","volume":"83","author":"J Balogh","year":"2021","unstructured":"Balogh, J., B\u00e9k\u00e9si, J., D\u00f3sa, G., Epstein, L., & Levin, A. (2021). A new lower bound for classic online bin packing. Algorithmica, 83(7), 2047\u20132062.","journal-title":"Algorithmica"},{"key":"854_CR9","unstructured":"Balogh, J., B\u00e9k\u00e9si, J., D\u00f3sa, G., Epstein, L., & Levin, A. (2024). More on online cardinality constrained bin packing with small cardinality bounds. Manuscript, 26 pages."},{"key":"854_CR10","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.jcss.2018.11.005","volume":"102","author":"J Balogh","year":"2019","unstructured":"Balogh, J., B\u00e9k\u00e9si, J., D\u00f3sa, G., Sgall, J., & van Stee, R. (2019). The optimal absolute ratio for online bin packing. Journal of Computer and System Sciences, 102, 1\u201317.","journal-title":"Journal of Computer and System Sciences"},{"key":"854_CR11","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.tcs.2012.04.017","volume":"440","author":"J Balogh","year":"2012","unstructured":"Balogh, J., B\u00e9k\u00e9si, J., & Galambos, G. (2012). New lower bounds for certain classes of bin packing algorithms. Theoretical Computer Science, 440, 1\u201313.","journal-title":"Theoretical Computer Science"},{"key":"854_CR12","doi-asserted-by":"publisher","first-page":"190","DOI":"10.1016\/j.ic.2016.06.001","volume":"249","author":"J B\u00e9k\u00e9si","year":"2016","unstructured":"B\u00e9k\u00e9si, J., D\u00f3sa, G., & Epstein, L. (2016). Bounds for online bin packing with cardinality constraints. Information and Computation, 249, 190\u2013204.","journal-title":"Information and Computation"},{"key":"854_CR13","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1016\/j.ic.2017.03.001","volume":"254","author":"H B\u00f6ckenhauer","year":"2017","unstructured":"B\u00f6ckenhauer, H., Komm, D., Kr\u00e1lovic, R., Kr\u00e1lovic, R., & M\u00f6mke, T. (2017). Online algorithms with advice: The tape model. Information and Computation, 254, 59\u201383.","journal-title":"Information and Computation"},{"issue":"6","key":"854_CR14","doi-asserted-by":"publisher","first-page":"1443","DOI":"10.1007\/s00224-017-9806-5","volume":"62","author":"J Boyar","year":"2018","unstructured":"Boyar, J., Favrholdt, L. M., Kudahl, C., & Mikkelsen, J. W. (2018). Weighted online problems with advice. Theory of Computing Systems, 62(6), 1443\u20131469.","journal-title":"Theory of Computing Systems"},{"issue":"1","key":"854_CR15","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., & L\u00f3pez-Ortiz, A. (2016). Online bin packing with advice. Algorithmica, 74(1), 507\u2013527.","journal-title":"Algorithmica"},{"key":"854_CR16","doi-asserted-by":"publisher","first-page":"58","DOI":"10.1002\/nav.10058","volume":"92","author":"A Caprara","year":"2003","unstructured":"Caprara, A., Kellerer, H., & Pferschy, U. (2003). Approximation schemes for ordered vector packing problems. Naval Research Logistics, 92, 58\u201369.","journal-title":"Naval Research Logistics"},{"key":"854_CR17","doi-asserted-by":"crossref","unstructured":"Dohrau, J. (2015). Online makespan scheduling with sublinear advice. In Proceedings of the 41st international conference on current trends in theory and practice of computer science (SOFSEM\u201915) (pp. 177\u2013188).","DOI":"10.1007\/978-3-662-46078-8_15"},{"key":"854_CR18","doi-asserted-by":"publisher","first-page":"149","DOI":"10.1016\/j.tcs.2015.06.046","volume":"596","author":"G D\u00f3sa","year":"2015","unstructured":"D\u00f3sa, G. (2015). The tight absolute bound of first fit in the parameterized case. Theoretical Computer Science, 596, 149\u2013154.","journal-title":"Theoretical Computer Science"},{"issue":"1","key":"854_CR19","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1137\/090766139","volume":"25","author":"G D\u00f3sa","year":"2011","unstructured":"D\u00f3sa, G., & Epstein, L. (2011). Preemptive online scheduling with reordering. SIAM Journal on Discrete Mathematics, 25(1), 21\u201349.","journal-title":"SIAM Journal on Discrete Mathematics"},{"key":"854_CR20","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1016\/j.jcss.2018.03.004","volume":"96","author":"G D\u00f3sa","year":"2018","unstructured":"D\u00f3sa, G., & Epstein, L. (2018). The tight asymptotic approximation ratio of First Fit for bin packing with cardinality constraints. Journal of Computer and System Sciences, 96, 33\u201349.","journal-title":"Journal of Computer and System Sciences"},{"key":"854_CR21","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1016\/j.tcs.2013.09.007","volume":"510","author":"G D\u00f3sa","year":"2013","unstructured":"D\u00f3sa, G., Li, R., Han, X., & Tuza, Z. (2013). Tight absolute bound for First Fit Decreasing bin-packing: $${FFD(L) \\le 11\/9 OPT(L) + 6\/9}$$. Theoretical Computer Science, 510, 13\u201361.","journal-title":"Theoretical Computer Science"},{"issue":"12","key":"854_CR22","doi-asserted-by":"publisher","first-page":"3537","DOI":"10.1007\/s00453-021-00852-5","volume":"83","author":"M Englert","year":"2021","unstructured":"Englert, M., Mezlaf, D., & Westermann, M. (2021). Online makespan scheduling with job migration on uniform machines. Algorithmica, 83(12), 3537\u20133566.","journal-title":"Algorithmica"},{"issue":"3","key":"854_CR23","doi-asserted-by":"publisher","first-page":"1220","DOI":"10.1137\/130919738","volume":"43","author":"M Englert","year":"2014","unstructured":"Englert, M., \u00d6zmen, D., & Westermann, M. (2014). The power of reordering for online minimum makespan scheduling. SIAM Journal on Computing, 43(3), 1220\u20131237.","journal-title":"SIAM Journal on Computing"},{"issue":"4","key":"854_CR24","doi-asserted-by":"publisher","first-page":"1015","DOI":"10.1137\/050639065","volume":"20","author":"L Epstein","year":"2006","unstructured":"Epstein, L. (2006). Online bin packing with cardinality constraints. SIAM Journal on Discrete Mathematics, 20(4), 1015\u20131030.","journal-title":"SIAM Journal on Discrete Mathematics"},{"key":"854_CR25","doi-asserted-by":"crossref","unstructured":"Epstein, L. (2023a). Parallel solutions for ordinal scheduling with a small number of machines. Journal of Combinatorial Optimization,46(1), 3.","DOI":"10.1007\/s10878-023-01069-8"},{"key":"854_CR26","doi-asserted-by":"crossref","unstructured":"Epstein, L. (2023b). Parallel solutions for preemptive makespan scheduling on two identical machines. Journal of Scheduling,26(1), 61\u201376.","DOI":"10.1007\/s10951-022-00764-4"},{"key":"854_CR27","doi-asserted-by":"crossref","unstructured":"Epstein, L. (2023c). Several methods of analysis for cardinality constrained bin packing. Theoretical Computer Science,942, 213\u2013229.","DOI":"10.1016\/j.tcs.2022.11.034"},{"issue":"6","key":"854_CR28","doi-asserted-by":"publisher","first-page":"3121","DOI":"10.1137\/090767613","volume":"20","author":"L Epstein","year":"2010","unstructured":"Epstein, L., & Levin, A. (2010). AFPTAS results for common variants of bin packing: A new method for handling the small items. SIAM Journal on Optimization, 20(6), 3121\u20133145.","journal-title":"SIAM Journal on Optimization"},{"issue":"3","key":"854_CR29","doi-asserted-by":"publisher","first-page":"1251","DOI":"10.1137\/100801901","volume":"25","author":"L Epstein","year":"2011","unstructured":"Epstein, L., Levin, A., Mestre, J., & Segev, D. (2011). Improved approximation guarantees for weighted matching in the semi-streaming model. SIAM Journal on Discrete Mathematics, 25(3), 1251\u20131265.","journal-title":"SIAM Journal on Discrete Mathematics"},{"issue":"3","key":"854_CR30","doi-asserted-by":"publisher","first-page":"1230","DOI":"10.1137\/100794006","volume":"25","author":"L Epstein","year":"2011","unstructured":"Epstein, L., Levin, A., & van Stee, R. (2011). Max-min online allocations with a reordering buffer. SIAM Journal on Discrete Mathematics, 25(3), 1230\u20131250.","journal-title":"SIAM Journal on Discrete Mathematics"},{"issue":"5","key":"854_CR31","doi-asserted-by":"publisher","first-page":"1709","DOI":"10.1137\/070683155","volume":"38","author":"J Feigenbaum","year":"2009","unstructured":"Feigenbaum, J., Kannan, S., McGregor, A., Suri, S., & Zhang, J. (2009). Graph distances in the data-stream model. SIAM Journal on Computing, 38(5), 1709\u20131727.","journal-title":"SIAM Journal on Computing"},{"issue":"1","key":"854_CR32","doi-asserted-by":"publisher","first-page":"296","DOI":"10.1007\/s00453-022-01030-x","volume":"85","author":"SP Fekete","year":"2023","unstructured":"Fekete, S. P., Grosse-Holz, J., Keldenich, P., & Schmidt, A. (2023). Parallel online algorithms for the bin packing problem. Algorithmica, 85(1), 296\u2013323.","journal-title":"Algorithmica"},{"issue":"1","key":"854_CR33","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1007\/s10878-013-9679-8","volume":"29","author":"H Fujiwara","year":"2015","unstructured":"Fujiwara, H., & Kobayashi, K. M. (2015). Improved lower bounds for the online bin packing problem with cardinality constraints. Journal of Combinatorial Optimization, 29(1), 67\u201387.","journal-title":"Journal of Combinatorial Optimization"},{"key":"854_CR34","unstructured":"Heydrich, S. & van Stee, R. (2016). Beating the harmonic lower bound for online bin packing. In Proceedings of 43rd international colloquium on automata, languages, and programming (ICALP2016) (pp. 41:1\u201341:14)."},{"key":"854_CR35","doi-asserted-by":"publisher","first-page":"256","DOI":"10.1093\/comjnl\/3.4.256","volume":"3","author":"DS Johnson","year":"1974","unstructured":"Johnson, D. S., Demers, A., Ullman, J. D., Garey, M. R., & Graham, R. L. (1974). Worst-case performance bounds for simple one-dimensional packing algorithms. SIAM Journal on Computing, 3, 256\u2013278.","journal-title":"SIAM Journal on Computing"},{"issue":"5","key":"854_CR36","doi-asserted-by":"publisher","first-page":"235","DOI":"10.1016\/S0167-6377(98)00005-4","volume":"21","author":"H Kellerer","year":"1997","unstructured":"Kellerer, H., Kotov, V., Speranza, M. G., & Tuza, Z. (1997). Semi on-line algorithms for the partition problem. Operations Research Letters, 21(5), 235\u2013242.","journal-title":"Operations Research Letters"},{"key":"854_CR37","doi-asserted-by":"publisher","first-page":"335","DOI":"10.1023\/A:1018947117526","volume":"92","author":"H Kellerer","year":"1999","unstructured":"Kellerer, H., & Pferschy, U. (1999). Cardinality constrained bin-packing problems. Annals of Operations Research, 92, 335\u2013348.","journal-title":"Annals of Operations Research"},{"issue":"4","key":"854_CR38","doi-asserted-by":"publisher","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. (1975). Analysis of several task-scheduling algorithms for a model of multiprogramming computer systems. Journal of the ACM, 22(4), 522\u2013550.","journal-title":"Journal of the ACM"},{"issue":"3","key":"854_CR39","doi-asserted-by":"publisher","first-page":"562","DOI":"10.1145\/3828.3833","volume":"32","author":"CC Lee","year":"1985","unstructured":"Lee, C. C., & Lee, D. T. (1985). A simple online bin packing algorithm. Journal of the ACM, 32(3), 562\u2013572.","journal-title":"Journal of the ACM"},{"key":"854_CR40","unstructured":"Mikkelsen, J. W. (2016). Randomization can be as helpful as a glimpse of the future in online computation. In Proceedings of the 43rd international colloquium on automata, languages, and programming, (ICALP\u201916) (pp. 39:1\u201339:14)."},{"key":"854_CR41","doi-asserted-by":"publisher","first-page":"305","DOI":"10.1016\/0196-6774(89)90031-X","volume":"10","author":"P Ramanan","year":"1989","unstructured":"Ramanan, P., Brown, D. J., Lee, C. C., & Lee, D. T. (1989). Online bin packing in linear time. Journal of Algorithms, 10, 305\u2013326.","journal-title":"Journal of Algorithms"},{"key":"854_CR42","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\u00e9n, A., & van Stee, R. (2015). Online algorithms with advice for bin packing and scheduling problems. Theoretical Computer Science, 600, 155\u2013170.","journal-title":"Theoretical Computer Science"},{"issue":"5","key":"854_CR43","doi-asserted-by":"publisher","first-page":"640","DOI":"10.1145\/585265.585269","volume":"49","author":"SS Seiden","year":"2002","unstructured":"Seiden, S. S. (2002). On the online bin packing problem. Journal of the ACM, 49(5), 640\u2013671.","journal-title":"Journal of the ACM"},{"issue":"5","key":"854_CR44","doi-asserted-by":"publisher","first-page":"277","DOI":"10.1016\/0020-0190(92)90223-I","volume":"43","author":"A van Vliet","year":"1992","unstructured":"van Vliet, A. (1992). An improved lower bound for online bin packing algorithms. Information Processing Letters, 43(5), 277\u2013284.","journal-title":"Information Processing Letters"},{"key":"854_CR45","doi-asserted-by":"publisher","first-page":"207","DOI":"10.1145\/322186.322187","volume":"27","author":"ACC Yao","year":"1980","unstructured":"Yao, A. C. C. (1980). New algorithms for bin packing. Journal of the ACM, 27, 207\u2013227.","journal-title":"Journal of the ACM"}],"container-title":["Journal of Scheduling"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10951-025-00854-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10951-025-00854-z","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10951-025-00854-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,3,16]],"date-time":"2026-03-16T10:41:21Z","timestamp":1773657681000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10951-025-00854-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,8,4]]},"references-count":45,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2026,2]]}},"alternative-id":["854"],"URL":"https:\/\/doi.org\/10.1007\/s10951-025-00854-z","relation":{},"ISSN":["1094-6136","1099-1425"],"issn-type":[{"value":"1094-6136","type":"print"},{"value":"1099-1425","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,8,4]]},"assertion":[{"value":"4 July 2025","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"4 August 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":"There are no Conflict of interest or Conflict of interest for this work.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}},{"value":"There is no software for this work.","order":3,"name":"Ethics","group":{"name":"EthicsHeading","label":"Code availability"}}]}}