{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,11]],"date-time":"2025-09-11T19:15:23Z","timestamp":1757618123128,"version":"3.44.0"},"reference-count":14,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2025,5,20]],"date-time":"2025-05-20T00:00:00Z","timestamp":1747699200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2025,5,20]],"date-time":"2025-05-20T00:00:00Z","timestamp":1747699200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100011019","name":"Nemzeti Kutat\u00e1si Fejleszt\u00e9si \u00e9s Innov\u00e1ci\u00f3s Hivatal","doi-asserted-by":"publisher","award":["SNN 129364"],"award-info":[{"award-number":["SNN 129364"]}],"id":[{"id":"10.13039\/501100011019","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100015498","name":"Innov\u00e1ci\u00f3s \u00e9s Technol\u00f3giai Miniszt\u00e9rium","doi-asserted-by":"publisher","award":["TKP2021-NVA-09"],"award-info":[{"award-number":["TKP2021-NVA-09"]}],"id":[{"id":"10.13039\/501100015498","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Ann Oper Res"],"published-print":{"date-parts":[[2025,7]]},"abstract":"<jats:title>Abstract<\/jats:title>\n          <jats:p>In this article we address the following problem. Given are a <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> square, a <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>$$2\\times 2$$<\/jats:tex-math>\n                <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mn>2<\/mml:mn>\n                    <mml:mo>\u00d7<\/mml:mo>\n                    <mml:mn>2<\/mml:mn>\n                  <\/mml:mrow>\n                <\/mml:math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula> square, and so on, finally a <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>$$n\\times n$$<\/jats:tex-math>\n                <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>n<\/mml:mi>\n                    <mml:mo>\u00d7<\/mml:mo>\n                    <mml:mi>n<\/mml:mi>\n                  <\/mml:mrow>\n                <\/mml:math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula> square. What is the biggest square that can be <jats:italic>covered<\/jats:italic> completely by this given set of \u201csmall\u201d squares? It is assumed that the small squares must stand parallel to the sides of the big square, and overlap is allowed. In contrast to the <jats:italic>packing<\/jats:italic> version of the problem (asking for the smallest square that can accommodate all small squares without overlap) which has been studied in several papers since the 1960\u2019s, the covering version of the problem seems new. We construct optimal coverings for small values of <jats:italic>n<\/jats:italic>. For moderately bigger <jats:italic>n<\/jats:italic> values we solve the problem optimally by a commercial mathematical programming solver, and for even bigger <jats:italic>n<\/jats:italic> values we give a heuristic algorithm that can find near optimal solutions. We also provide an expansion-algorithm, that from a given good cover using consecutive squares up to size <jats:italic>n<\/jats:italic>, can generate a cover for a larger square using small squares up to size <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>$$n+1$$<\/jats:tex-math>\n                <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:mn>1<\/mml:mn>\n                  <\/mml:mrow>\n                <\/mml:math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula>. Finally we prove that a simple covering policy can generate an asymptotically optimal covering.<\/jats:p>","DOI":"10.1007\/s10479-025-06633-5","type":"journal-article","created":{"date-parts":[[2025,5,20]],"date-time":"2025-05-20T11:34:04Z","timestamp":1747740844000},"page":"911-926","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Covering a square with consecutive squares"],"prefix":"10.1007","volume":"350","author":[{"given":"Janos","family":"Balogh","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4909-6694","authenticated-orcid":false,"given":"Gyorgy","family":"Dosa","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Lars Magnus","family":"Hvattum","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tomas Attila","family":"Olaj","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Istvan","family":"Szalkai","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Zsolt","family":"Tuza","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2025,5,20]]},"reference":[{"key":"6633_CR1","doi-asserted-by":"publisher","first-page":"1056","DOI":"10.1016\/j.ejor.2023.01.030","volume":"308","author":"G Abraham","year":"2023","unstructured":"Abraham, G., Dosa, G., Hvattum, L. M., Olaj, T. A., & Tuza, Z. S. (2023). The board packing problem. European Journal of Operational Research, 308, 1056\u20131073.","journal-title":"European Journal of Operational Research"},{"key":"6633_CR2","doi-asserted-by":"publisher","first-page":"2775","DOI":"10.1007\/s11590-022-01858-w","volume":"16","author":"J Balogh","year":"2022","unstructured":"Balogh, J., Dosa, G., Hvattum, L. M., Olaj, T., & Tuza, Z. S. (2022). Guillotine cutting is asymptotically optimal for packing consecutive squares. Optimization Letters, 16, 2775\u20132785. https:\/\/doi.org\/10.1007\/s11590-022-01858-w","journal-title":"Optimization Letters"},{"key":"6633_CR3","unstructured":"Buchwald, T., & Scheithauer, G. (2016). A 5\/9 theorem on packing squares into a square. Preprint MATH-NM-04-2016, TU Dresden."},{"key":"6633_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. (1980). Performance bounds for level-oriented two-dimensional packing algorithms. SIAM Journal on Computing, 9, 808\u2013826.","journal-title":"SIAM Journal on Computing"},{"key":"6633_CR5","first-page":"10","volume-title":"Proceedings of the Pannonian Conference on Advances in Information Technology (PCIT 2020)","author":"G D\u00f3sa","year":"2020","unstructured":"D\u00f3sa, G., Hvattum, L. M., Olaj, T., & Tuza, Z. S. (2020). The board packing problem: Packing rectangles into a board to maximize profit. In I. Vass\u00e1nyi (Ed.), Proceedings of the Pannonian Conference on Advances in Information Technology (PCIT 2020) (pp. 10\u201316). Veszpr\u00e9m, Hungary: University of Pannonia."},{"issue":"3","key":"6633_CR6","doi-asserted-by":"publisher","first-page":"264","DOI":"10.1038\/scientificamerican0966-264","volume":"215","author":"M Gardner","year":"1966","unstructured":"Gardner, M. (1966). Mathematical games: The problem of Mrs. Perkins\u2019 quilt, and answers to last month\u2019s puzzles. Scientific American, 215(3), 264\u2013272.","journal-title":"Scientific American"},{"key":"6633_CR7","unstructured":"Gardner, M. (1975). Mrs. Perkins\u2019 quilt and other square-packing problems. In Mathematical Carnival. New York: Alfred A. Knopf (pp. 139\u2013149)."},{"key":"6633_CR8","unstructured":"Korf, R. E. (2003). Optimal rectangle packing: Initial results. In: Proceedings of the 13th International Conference on Automated Planning and Scheduling (ICAPS 2003), (pp. 287\u2013295)."},{"key":"6633_CR9","unstructured":"Korf, R. E. (2004). Optimal rectangle packing: New results. In: Proceedings of the 14th International Conference on Automated Planning and Scheduling (ICAPS 2004), (pp. 142\u2013149)."},{"key":"6633_CR10","unstructured":"Moffitt, M. D., & Pollack, M. E. (2006). Optimal rectangle packing: a meta-CSP approach. In: Proceedings of the 16th International Conference on Automated Planning and Scheduling (ICAPS 2006), (pp. 93\u2013102)."},{"key":"6633_CR11","doi-asserted-by":"crossref","unstructured":"Simonis, H., & O\u2019Sullivan, B. (2008). Search strategies for rectangle packing. In: Constraint Programming 2008, Lecture Notes in Computer Science, (vol. 5202 pp. 52\u201366).","DOI":"10.1007\/978-3-540-85958-1_4"},{"key":"6633_CR12","doi-asserted-by":"publisher","DOI":"10.1016\/j.cor.2021.105643","volume":"140","author":"T Vidal","year":"2022","unstructured":"Vidal, T. (2022). Hybrid genetic search for the CVRP: Open-source implementation and SWAP* neighborhood. Computers and Operations Research, 140, Article 105643.","journal-title":"Computers and Operations Research"},{"key":"6633_CR13","unstructured":"The on-line encyclopedia of integer sequences, sequence a005842. Published electronically at http:\/\/oeis.org, accessed: 26 March 2021."},{"key":"6633_CR14","first-page":"1","volume":"48","author":"G Watson","year":"1918","unstructured":"Watson, G. (1918). The problem of the square pyramid. Messenger of Mathematics, New Series, 48, 1\u201322.","journal-title":"Messenger of Mathematics, New Series"}],"container-title":["Annals of Operations Research"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10479-025-06633-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10479-025-06633-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10479-025-06633-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,9,6]],"date-time":"2025-09-06T15:10:08Z","timestamp":1757171408000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10479-025-06633-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,5,20]]},"references-count":14,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2025,7]]}},"alternative-id":["6633"],"URL":"https:\/\/doi.org\/10.1007\/s10479-025-06633-5","relation":{},"ISSN":["0254-5330","1572-9338"],"issn-type":[{"type":"print","value":"0254-5330"},{"type":"electronic","value":"1572-9338"}],"subject":[],"published":{"date-parts":[[2025,5,20]]},"assertion":[{"value":"11 January 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"24 April 2025","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"20 May 2025","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":"Conflict of Interest"}},{"value":"This article does not contain any studies with human participants or animals performed by any of the authors.","order":3,"name":"Ethics","group":{"name":"EthicsHeading","label":"Ethical approval"}},{"value":"Not applicable.","order":4,"name":"Ethics","group":{"name":"EthicsHeading","label":"Informed consent"}}]}}