{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,18]],"date-time":"2026-05-18T07:08:58Z","timestamp":1779088138382,"version":"3.51.4"},"reference-count":11,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[2026,5,18]],"date-time":"2026-05-18T00:00:00Z","timestamp":1779062400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2026,5,18]],"date-time":"2026-05-18T00:00:00Z","timestamp":1779062400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100003593","name":"Conselho Nacional de Desenvolvimento Cient\u00edfico e Tecnol\u00f3gico","doi-asserted-by":"publisher","award":["163644\/2021-7"],"award-info":[{"award-number":["163644\/2021-7"]}],"id":[{"id":"10.13039\/501100003593","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003593","name":"Conselho Nacional de Desenvolvimento Cient\u00edfico e Tecnol\u00f3gico","doi-asserted-by":"publisher","award":["312345\/2023-2"],"award-info":[{"award-number":["312345\/2023-2"]}],"id":[{"id":"10.13039\/501100003593","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001807","name":"Funda\u00e7\u00e3o de Amparo \u00e0 Pesquisa do Estado de S\u00e3o Paulo","doi-asserted-by":"publisher","award":["2022\/05803-3"],"award-info":[{"award-number":["2022\/05803-3"]}],"id":[{"id":"10.13039\/501100001807","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100006417","name":"Fundo de Apoio ao Ensino, \u00e0 Pesquisa e Extens\u00e3o, Universidade Estadual de Campinas","doi-asserted-by":"publisher","award":["2372\/23"],"award-info":[{"award-number":["2372\/23"]}],"id":[{"id":"10.13039\/501100006417","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100002322","name":"Coordena\u00e7\u00e3o de Aperfei\u00e7oamento de Pessoal de N\u00edvel Superior","doi-asserted-by":"publisher","award":["88887.602019\/2021-00"],"award-info":[{"award-number":["88887.602019\/2021-00"]}],"id":[{"id":"10.13039\/501100002322","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100002322","name":"Coordena\u00e7\u00e3o de Aperfei\u00e7oamento de Pessoal de N\u00edvel Superior","doi-asserted-by":"publisher","award":["404779\/2025-5"],"award-info":[{"award-number":["404779\/2025-5"]}],"id":[{"id":"10.13039\/501100002322","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2026,7]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>\n                    In this work, we study the Square Min-Sum Bin Packing Problem (SMSBPP), where a list of\u00a0\n                    <jats:italic>n<\/jats:italic>\n                    square items has to be packed into square bins of dimensions\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:tex-math>$$1 \\times 1$$<\/jats:tex-math>\n                        <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <mml:mrow>\n                            <mml:mn>1<\/mml:mn>\n                            <mml:mo>\u00d7<\/mml:mo>\n                            <mml:mn>1<\/mml:mn>\n                          <\/mml:mrow>\n                        <\/mml:math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    with no overlap between the areas of the items. The bins are indexed (starting at one) and the cost of packing each item is equal to the index of the bin in which it is placed. The objective is to minimize the total cost of packing all items, which is equivalent to minimizing the average cost of items. The problem has applications in minimizing the average time of logistic operations such as cutting stock and delivery of products. We prove that classic algorithms for two-dimensional bin packing that order items in non-increasing order of size, such as Next Fit Decreasing Height or Any Fit Decreasing Height heuristics, can have an arbitrarily bad performance for SMSBPP. We, then, present an algorithm with an approximation ratio of\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:tex-math>$$\\sqrt{205}-12+\\delta $$<\/jats:tex-math>\n                        <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <mml:mrow>\n                            <mml:msqrt>\n                              <mml:mn>205<\/mml:mn>\n                            <\/mml:msqrt>\n                            <mml:mo>-<\/mml:mo>\n                            <mml:mn>12<\/mml:mn>\n                            <mml:mo>+<\/mml:mo>\n                            <mml:mi>\u03b4<\/mml:mi>\n                          <\/mml:mrow>\n                        <\/mml:math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    (\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:tex-math>$$\\approx 2.3178+\\delta $$<\/jats:tex-math>\n                        <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <mml:mrow>\n                            <mml:mo>\u2248<\/mml:mo>\n                            <mml:mn>2.3178<\/mml:mn>\n                            <mml:mo>+<\/mml:mo>\n                            <mml:mi>\u03b4<\/mml:mi>\n                          <\/mml:mrow>\n                        <\/mml:math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    ), for any\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:tex-math>$$\\delta &gt; 0$$<\/jats:tex-math>\n                        <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <mml:mrow>\n                            <mml:mi>\u03b4<\/mml:mi>\n                            <mml:mo>&gt;<\/mml:mo>\n                            <mml:mn>0<\/mml:mn>\n                          <\/mml:mrow>\n                        <\/mml:math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    , and running time\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:tex-math>$$O(n \\log n)$$<\/jats:tex-math>\n                        <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <mml:mrow>\n                            <mml:mi>O<\/mml:mi>\n                            <mml:mo>(<\/mml:mo>\n                            <mml:mi>n<\/mml:mi>\n                            <mml:mo>log<\/mml:mo>\n                            <mml:mi>n<\/mml:mi>\n                            <mml:mo>)<\/mml:mo>\n                          <\/mml:mrow>\n                        <\/mml:math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    . Finally, we also present a PTAS for the problem.\n                  <\/jats:p>","DOI":"10.1007\/s10878-026-01425-4","type":"journal-article","created":{"date-parts":[[2026,5,18]],"date-time":"2026-05-18T06:31:12Z","timestamp":1779085872000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Approximation algorithms for the Square Min-Sum Bin Packing Problem"],"prefix":"10.1007","volume":"51","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-6197-603X","authenticated-orcid":false,"given":"Rachel","family":"Vanucchi Saraiva","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0472-4810","authenticated-orcid":false,"given":"Rafael C. S.","family":"Schouery","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2026,5,18]]},"reference":[{"issue":"1","key":"1425_CR1","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1287\/moor.1050.0168","volume":"31","author":"N Bansal","year":"2006","unstructured":"Bansal N, Correa JR, Kenyon C, Sviridenko M (2006) Bin packing in multiple dimensions: Inapproximability results and approximation schemes. Math Oper Res 31(1):31\u201349. https:\/\/doi.org\/10.1287\/moor.1050.0168","journal-title":"Math Oper Res"},{"key":"1425_CR2","doi-asserted-by":"publisher","first-page":"63","DOI":"10.1016\/j.cosrev.2016.12.001","volume":"24","author":"HI Christensen","year":"2017","unstructured":"Christensen HI, Khan A, Pokutta S, Tetali P (2017) Approximation and online algorithms for multidimensional bin packing: A survey. Computer Science Review 24:63\u201379. https:\/\/doi.org\/10.1016\/j.cosrev.2016.12.001","journal-title":"Computer Science Review"},{"issue":"4","key":"1425_CR3","doi-asserted-by":"publisher","first-page":"808","DOI":"10.1137\/0209062","volume":"9","author":"EG Coffman Jr","year":"1980","unstructured":"Coffman EG Jr, Garey MR, Johnson DS, Tarjan RE (1980) Performance bounds for level-oriented two-dimensional packing algorithms. SIAM J Comput 9(4):808\u2013826. https:\/\/doi.org\/10.1137\/0209062","journal-title":"SIAM J Comput"},{"issue":"1","key":"1425_CR4","first-page":"11","volume":"1","author":"U Eliiyi","year":"2009","unstructured":"Eliiyi U, Eliiyi DT (2009) Applications of bin packing models through the supply chain. International Journal of Business and Management Studies 1(1):11\u201319","journal-title":"International Journal of Business and Management Studies"},{"key":"1425_CR5","doi-asserted-by":"publisher","unstructured":"Epstein L, Levin A (2007) Minimum weighted sum bin packing. In: International Workshop on Approximation and Online Algorithms, pp 218\u2013231, https:\/\/doi.org\/10.1007\/978-3-540-77918-6","DOI":"10.1007\/978-3-540-77918-6"},{"issue":"2","key":"1425_CR6","doi-asserted-by":"publisher","first-page":"508","DOI":"10.1007\/s10878-018-0310-x","volume":"36","author":"L Epstein","year":"2018","unstructured":"Epstein L, Johnson DS, Levin A (2018) Min-sum bin packing. J Comb Optim 36(2):508\u2013531. https:\/\/doi.org\/10.1007\/s10878-018-0310-x","journal-title":"J Comb Optim"},{"issue":"2","key":"1425_CR7","first-page":"223","volume":"19","author":"CE Ferreira","year":"1999","unstructured":"Ferreira CE, Miyazawa FK, Wakabayashi Y (1999) Packing squares into squares Pesquisa Operacional 19(2):223\u2013237","journal-title":"Packing squares into squares Pesquisa Operacional"},{"issue":"1","key":"1425_CR8","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.ejor.2021.06.012","volume":"298","author":"JW Fowler","year":"2022","unstructured":"Fowler JW, M\u00f6nch L (2022) A survey of scheduling with parallel batch (p-batch) processing. Eur J Oper Res 298(1):1\u201324. https:\/\/doi.org\/10.1016\/j.ejor.2021.06.012","journal-title":"Eur J Oper Res"},{"key":"1425_CR9","doi-asserted-by":"publisher","unstructured":"Graham RL, Lawler EL, Lenstra JK, Kan AR (1979) Optimization and approximation in deterministic sequencing and scheduling: a survey. In: Annals of discrete mathematics, vol\u00a05, Elsevier, pp 287\u2013326, https:\/\/doi.org\/10.1016\/S0167-5060(08)70356-X","DOI":"10.1016\/S0167-5060(08)70356-X"},{"key":"1425_CR10","doi-asserted-by":"publisher","first-page":"103","DOI":"10.4064\/cm-17-1-103-110","volume":"17","author":"JW Moon","year":"1967","unstructured":"Moon JW, Moser L (1967) Some packing and covering theorems. Colloq Math 17:103\u2013110","journal-title":"Colloq Math"},{"issue":"6","key":"1425_CR11","doi-asserted-by":"publisher","first-page":"535","DOI":"10.1016\/j.orl.2004.02.003","volume":"32","author":"R Van Stee","year":"2004","unstructured":"Van Stee R (2004) An approximation algorithm for square packing. Oper Res Lett 32(6):535\u2013539. https:\/\/doi.org\/10.1016\/j.orl.2004.02.003","journal-title":"Oper Res Lett"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-026-01425-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10878-026-01425-4","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-026-01425-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,5,18]],"date-time":"2026-05-18T06:31:13Z","timestamp":1779085873000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10878-026-01425-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,5,18]]},"references-count":11,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2026,7]]}},"alternative-id":["1425"],"URL":"https:\/\/doi.org\/10.1007\/s10878-026-01425-4","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"value":"1382-6905","type":"print"},{"value":"1573-2886","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,5,18]]},"assertion":[{"value":"9 July 2025","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"6 May 2026","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"18 May 2026","order":3,"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 that they have no conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflicts of Interest"}}],"article-number":"49"}}