dc.contributor.author | Balogh, János | |
dc.contributor.author | Dósa, György | |
dc.contributor.author | Hvattum, Lars Magnus | |
dc.contributor.author | Olaj, Tomas | |
dc.contributor.author | Tuza, Zsolt | |
dc.date.accessioned | 2024-03-13T11:53:32Z | |
dc.date.available | 2024-03-13T11:53:32Z | |
dc.date.created | 2022-04-10T15:56:09Z | |
dc.date.issued | 2022 | |
dc.identifier.citation | Optimization Letters. 2022, 16 (9), 2775-2785. | en_US |
dc.identifier.issn | 1862-4472 | |
dc.identifier.uri | https://hdl.handle.net/11250/3122119 | |
dc.description.abstract | 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 1, 2,..., n can be packed without overlap. Constructions are known for a certain range of n, and summing up the areas yields that a packing in a square of size smaller than N :=√n(n + 1)(2n + 1)/6) is not possible. Here we prove that an asymptotically minimal packing exists in a square of size N +cn+O(√n) with c < 1, 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. Keywords: Square packing · Guillotine cut · Asymptotic analysis · Gardner’s problem · Square the square · Recursive algorithm. | en_US |
dc.language.iso | eng | en_US |
dc.relation.uri | https://doi.org/10.1007/s11590-022-01858-w | |
dc.rights | Navngivelse 4.0 Internasjonal | * |
dc.rights.uri | http://creativecommons.org/licenses/by/4.0/deed.no | * |
dc.title | Guillotine cutting is asymptotically optimal for packing consecutive squares | en_US |
dc.type | Peer reviewed | en_US |
dc.type | Journal article | en_US |
dc.description.version | publishedVersion | en_US |
dc.source.pagenumber | 2775-2785 | en_US |
dc.source.volume | 16 | en_US |
dc.source.journal | Optimization Letters | en_US |
dc.source.issue | 9 | en_US |
dc.identifier.doi | 10.1007/s11590-022-01858-w | |
dc.identifier.cristin | 2016517 | |
cristin.ispublished | true | |
cristin.fulltext | original | |
cristin.qualitycode | 1 | |