Guillotine cutting is asymptotically optimal for packing consecutive squares

Autor: János Balogh, György Dósa, Lars Magnus Hvattum, Tomas Olaj, Zsolt Tuza
Rok vydání: 2022
Předmět:
Zdroj: Optimization Letters. 16:2775-2785
ISSN: 1862-4480
1862-4472
DOI: 10.1007/s11590-022-01858-w
Popis: 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,\dots ,n$$ 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:= \!\sqrt{n(n+1)(2n+1)/6)} $$ N : = n ( n + 1 ) ( 2 n + 1 ) / 6 ) is not possible. Here we prove that an asymptotically minimal packing exists in a square of size $$N+cn+O(\!\sqrt{n})$$ N + c n + O ( n ) with $$c 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.
Databáze: OpenAIRE
Externí odkaz: