{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,8]],"date-time":"2025-09-08T05:35:28Z","timestamp":1757309728832,"version":"3.37.3"},"reference-count":23,"publisher":"Springer Science and Business Media LLC","issue":"9","license":[{"start":{"date-parts":[[2022,3,19]],"date-time":"2022-03-19T00:00:00Z","timestamp":1647648000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,3,19]],"date-time":"2022-03-19T00:00:00Z","timestamp":1647648000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100012550","name":"Nemzeti Kutat\u00e1si, Fejleszt\u00e9si \u00e9s Innovaci\u00f3s Alap","doi-asserted-by":"publisher","award":["SNN 129364"],"award-info":[{"award-number":["SNN 129364"]}],"id":[{"id":"10.13039\/501100012550","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Extending the activities of the HU-MATHS-IN Hungarian Industrial and Innovation Mathematical Service Network","award":["EFOP- 3.6.2-16-2017-00015"],"award-info":[{"award-number":["EFOP- 3.6.2-16-2017-00015"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Optim Lett"],"published-print":{"date-parts":[[2022,12]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>More than half a century ago Martin Gardner popularized a question leading to the benchmark problem of determining the minimum side length of a square into which the squares of sizes <jats:inline-formula><jats:alternatives><jats:tex-math>$$1,2,\\dots ,n$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mn>1<\/mml:mn>\n                    <mml:mo>,<\/mml:mo>\n                    <mml:mn>2<\/mml:mn>\n                    <mml:mo>,<\/mml:mo>\n                    <mml:mo>\u22ef<\/mml:mo>\n                    <mml:mo>,<\/mml:mo>\n                    <mml:mi>n<\/mml:mi>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> can be packed without overlap. Constructions are known for a certain range of <jats:italic>n<\/jats:italic>, and summing up the areas yields that a packing in a square of size smaller than <jats:inline-formula><jats:alternatives><jats:tex-math>$$N:= \\!\\sqrt{n(n+1)(2n+1)\/6)} $$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>N<\/mml:mi>\n                    <mml:mo>:<\/mml:mo>\n                    <mml:mo>=<\/mml:mo>\n                    <mml:mspace\/>\n                    <mml:msqrt>\n                      <mml:mrow>\n                        <mml:mi>n<\/mml:mi>\n                        <mml:mo>(<\/mml:mo>\n                        <mml:mi>n<\/mml:mi>\n                        <mml:mo>+<\/mml:mo>\n                        <mml:mn>1<\/mml:mn>\n                        <mml:mo>)<\/mml:mo>\n                        <mml:mo>(<\/mml:mo>\n                        <mml:mn>2<\/mml:mn>\n                        <mml:mi>n<\/mml:mi>\n                        <mml:mo>+<\/mml:mo>\n                        <mml:mn>1<\/mml:mn>\n                        <mml:mo>)<\/mml:mo>\n                        <mml:mo>\/<\/mml:mo>\n                        <mml:mn>6<\/mml:mn>\n                        <mml:mo>)<\/mml:mo>\n                      <\/mml:mrow>\n                    <\/mml:msqrt>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> is not possible. Here we prove that an asymptotically minimal packing exists in a square of size <jats:inline-formula><jats:alternatives><jats:tex-math>$$N+cn+O(\\!\\sqrt{n})$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>N<\/mml:mi>\n                    <mml:mo>+<\/mml:mo>\n                    <mml:mi>c<\/mml:mi>\n                    <mml:mi>n<\/mml:mi>\n                    <mml:mo>+<\/mml:mo>\n                    <mml:mi>O<\/mml:mi>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:mspace\/>\n                    <mml:msqrt>\n                      <mml:mi>n<\/mml:mi>\n                    <\/mml:msqrt>\n                    <mml:mo>)<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> with <jats:inline-formula><jats:alternatives><jats:tex-math>$$c&lt;1$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>c<\/mml:mi>\n                    <mml:mo>&lt;<\/mml:mo>\n                    <mml:mn>1<\/mml:mn>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, and such a packing is achievable with guillotine-cuts. An improved construction is also given for the case where the constraint of guillotine cutting is dropped.<\/jats:p>","DOI":"10.1007\/s11590-022-01858-w","type":"journal-article","created":{"date-parts":[[2022,3,19]],"date-time":"2022-03-19T07:02:51Z","timestamp":1647673371000},"page":"2775-2785","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Guillotine cutting is asymptotically optimal for packing consecutive squares"],"prefix":"10.1007","volume":"16","author":[{"given":"J\u00e1nos","family":"Balogh","sequence":"first","affiliation":[]},{"given":"Gy\u00f6rgy","family":"D\u00f3sa","sequence":"additional","affiliation":[]},{"given":"Lars Magnus","family":"Hvattum","sequence":"additional","affiliation":[]},{"given":"Tomas","family":"Olaj","sequence":"additional","affiliation":[]},{"given":"Zsolt","family":"Tuza","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,3,19]]},"reference":[{"key":"1858_CR1","first-page":"1","volume":"28","author":"V B\u00e1lint","year":"2016","unstructured":"B\u00e1lint, V., Adamko, P.: Universal asymptotical results on packing of cubes. Stud. Univ. \u017dilina Math. Ser. 28, 1\u20134 (2016)","journal-title":"Stud. Univ. \u017dilina Math. Ser."},{"key":"1858_CR2","unstructured":"Buchwald, T., Scheithauer, G.: A 5\/9 Theorem on Packing Squares into a Square. Preprint MATH-NM-04-2016. TU Dresden (2016). http:\/\/www.math.tu-dresden.de\/scheith\/ABSTRACTS\/dREPRINTS\/16-5-9-Theorem.pdf"},{"issue":"2","key":"1858_CR3","doi-asserted-by":"publisher","first-page":"158","DOI":"10.1006\/jcta.2000.3058","volume":"92","author":"A Chalcraft","year":"2000","unstructured":"Chalcraft, A.: Perfect square packings. J. Combin. Theory Ser. A 92(2), 158\u2013172 (2000)","journal-title":"J. Combin. Theory Ser. A"},{"key":"1858_CR4","doi-asserted-by":"publisher","first-page":"808","DOI":"10.1137\/0209062","volume":"9","author":"EG Coffman Jr","year":"1980","unstructured":"Coffman, E.G., Jr., Garey, M.R., Johnson, D.S., Tarjan, R.E.: Performance bounds for level-oriented two-dimensional packing algorithms. SIAM J. Comput. 9, 808\u2013826 (1980)","journal-title":"SIAM J. Comput."},{"key":"1858_CR5","doi-asserted-by":"crossref","unstructured":"Gardner, M.: Mathematical games: the problem of Mrs. Perkins\u2019 quilt, and answers to last month\u2019s puzzles. Sci. Am. 215(3), 264\u2013272 (1966)","DOI":"10.1038\/scientificamerican0966-264"},{"key":"1858_CR6","unstructured":"Gardner, M.: Mrs. Perkins\u2019 quilt and other square-packing problems. In: Mathematical Carnival, pp. 139\u2013149. Alfred A. Knopf (1975)"},{"issue":"8","key":"1858_CR7","doi-asserted-by":"publisher","first-page":"456","DOI":"10.1016\/j.comgeo.2011.05.001","volume":"44","author":"S Hougardy","year":"2011","unstructured":"Hougardy, S.: On packing squares into a rectangle. Comput. Geom. 44(8), 456\u2013463 (2011)","journal-title":"Comput. Geom."},{"key":"1858_CR8","unstructured":"Hougardy, S.: A scale invariant algorithm for packing rectangles perfectly. In: Proceedings of the Fourth International Workshop on Bin Packing and Placement Constraints (BPPC\u201912) (2012). http:\/\/www.or.uni-bonn.de\/hougardy\/paper\/PerfectPacking.pdf"},{"key":"1858_CR9","doi-asserted-by":"publisher","first-page":"1009","DOI":"10.33048\/semi.2020.17.075","volume":"17","author":"J Januszewski","year":"2020","unstructured":"Januszewski, J., Zielonka, L.: A note on perfect packing of $$d$$-dimensional cubes. Sibirskie \u00c8lektronnye Matematicheskie Izvestiya Siberian Electron. Math. Rep. 17, 1009\u20131012 (2020)","journal-title":"Sibirskie \u00c8lektronnye Matematicheskie Izvestiya Siberian Electron. Math. Rep."},{"issue":"2","key":"1858_CR10","doi-asserted-by":"publisher","first-page":"375","DOI":"10.1007\/s10474-018-0858-z","volume":"156","author":"A Jo\u00f3s","year":"2018","unstructured":"Jo\u00f3s, A.: Perfect packing of cubes. Acta Math. Hungar. 156(2), 375\u2013384 (2018)","journal-title":"Acta Math. Hungar."},{"key":"1858_CR11","doi-asserted-by":"publisher","first-page":"853","DOI":"10.33048\/semi.2020.17.062","volume":"17","author":"A Jo\u00f3s","year":"2020","unstructured":"Jo\u00f3s, A.: Perfect packing of $$d$$-cubes. Sibirskie \u00c8lektronnye Matematicheskie Izvestiya Siberian Electron. Math. Rep. 17, 853\u2013864 (2020)","journal-title":"Sibirskie \u00c8lektronnye Matematicheskie Izvestiya Siberian Electron. Math. Rep."},{"key":"1858_CR12","doi-asserted-by":"crossref","unstructured":"Kazanskiy, N., Kuznetsov, M.: The necessary bound of rectangle\u2019s square for packing into this any system of five and more than five finite quantity squares with total area 1. Proc. Eng. 201, 801\u2013805 (2017)","DOI":"10.1016\/j.proeng.2017.09.601"},{"key":"1858_CR13","doi-asserted-by":"crossref","unstructured":"Kleitman, D.J., Krieger, M.M.: An optimal bound for two dimensional bin packing. In: Proceedings of the 16th Annual Symposium on Foundations of Computer Science. IEEE, Long Beach, pp. 163\u2013168 (1975)","DOI":"10.1109\/SFCS.1975.6"},{"key":"1858_CR14","unstructured":"Korf, R.E.: Optimal rectangle packing: initial results. In: Proceedings of the 13th International Conference on Automated Planning and Scheduling (ICAPS 2003), pp. 287\u2013295 (2003)"},{"key":"1858_CR15","unstructured":"Korf, R.E.: Optimal rectangle packing: new results. In: Proceedings of the 14th International Conference on Automated Planning and Scheduling (ICAPS 2004), pp. 142\u2013149 (2004)"},{"key":"1858_CR16","unstructured":"Moffitt, M.D., Pollack, M.E.: Optimal rectangle packing: a meta-CSP approach. In: Long, D., Smith, S.F., Borrajo, D., McCluskey, L. (eds) Proceedings of the Sixteenth International Conference on Automated Planning and Scheduling (ICAPS 2006), pp. 93\u2013102 (2006)"},{"issue":"1","key":"1858_CR17","doi-asserted-by":"publisher","first-page":"103","DOI":"10.4064\/cm-17-1-103-110","volume":"17","author":"JW Moon","year":"1967","unstructured":"Moon, J.W., Moser, L.: Some packing and covering theorems. Colloquium Math. 17(1), 103\u2013110 (1967)","journal-title":"Colloquium Math."},{"key":"1858_CR18","first-page":"75","volume":"32","author":"P Novotn\u00fd","year":"1996","unstructured":"Novotn\u00fd, P.: On packing of squares into a rectangle. Archivum Math. 32, 75\u201383 (1996)","journal-title":"Archivum Math."},{"key":"1858_CR19","first-page":"199","volume":"19","author":"P Novotn\u00fd","year":"1999","unstructured":"Novotn\u00fd, P.: On packing of four and five squares into a rectangle. Note di Matematica 19, 199\u2013206 (1999)","journal-title":"Note di Matematica"},{"key":"1858_CR20","doi-asserted-by":"publisher","unstructured":"Sedlia\u010dkov\u00e1, Z., Adamko, P.: Packing three cubes in $$d$$-dimensional space. Mathematics 9 2046(2021), 9 pp. https:\/\/doi.org\/10.3390\/math9172046","DOI":"10.3390\/math9172046"},{"key":"1858_CR21","doi-asserted-by":"crossref","unstructured":"Simonis, H., O\u2019Sullivan, B.: Search strategies for rectangle packing. In: Stuckey, P.J. (ed) Constraint Programming 2008, volume 5202 of Lecture Notes in Computer Science, pp. 52\u201366 (2008)","DOI":"10.1007\/978-3-540-85958-1_4"},{"key":"1858_CR22","unstructured":"The on-line encyclopedia of integer sequences, sequence a005842. Published electronically at http:\/\/oeis.org, accessed: 26 March 2021"},{"key":"1858_CR23","first-page":"1","volume":"48","author":"G Watson","year":"1918","unstructured":"Watson, G.: Messenger of mathematics. New Ser. 48, 1\u201322 (1918)","journal-title":"New Ser."}],"container-title":["Optimization Letters"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11590-022-01858-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s11590-022-01858-w\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11590-022-01858-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,10,27]],"date-time":"2022-10-27T13:03:48Z","timestamp":1666875828000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s11590-022-01858-w"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,3,19]]},"references-count":23,"journal-issue":{"issue":"9","published-print":{"date-parts":[[2022,12]]}},"alternative-id":["1858"],"URL":"https:\/\/doi.org\/10.1007\/s11590-022-01858-w","relation":{},"ISSN":["1862-4472","1862-4480"],"issn-type":[{"type":"print","value":"1862-4472"},{"type":"electronic","value":"1862-4480"}],"subject":[],"published":{"date-parts":[[2022,3,19]]},"assertion":[{"value":"6 April 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"24 January 2022","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"19 March 2022","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}