Covering a square with consecutive squares
In this article we address the following problem. Given are a 1\times 1 1 × 1 square, a 2\times 2 2 × 2 square, and so on, finally a n\times n n × n square. What is the biggest square that can be covered completely by this given set of “small” squares? It is assumed that the small squares must stand...
Elmentve itt :
| Szerzők: | |
|---|---|
| Dokumentumtípus: | Cikk |
| Megjelent: |
2025
|
| Sorozat: | ANNALS OF OPERATIONS RESEARCH
350 No. 3 |
| Tárgyszavak: | |
| doi: | 10.1007/s10479-025-06633-5 |
| mtmt: | 36153271 |
| Online Access: | http://publicatio.bibl.u-szeged.hu/36974 |
| LEADER | 02189nab a2200289 i 4500 | ||
|---|---|---|---|
| 001 | publ36974 | ||
| 005 | 20251103141450.0 | ||
| 008 | 250612s2025 hu o 000 eng d | ||
| 022 | |a 0254-5330 | ||
| 024 | 7 | |a 10.1007/s10479-025-06633-5 |2 doi | |
| 024 | 7 | |a 36153271 |2 mtmt | |
| 040 | |a SZTE Publicatio Repozitórium |b hun | ||
| 041 | |a eng | ||
| 100 | 1 | |a Balogh János | |
| 245 | 1 | 0 | |a Covering a square with consecutive squares |h [elektronikus dokumentum] / |c Balogh János |
| 260 | |c 2025 | ||
| 300 | |a 911-926 | ||
| 490 | 0 | |a ANNALS OF OPERATIONS RESEARCH |v 350 No. 3 | |
| 520 | 3 | |a In this article we address the following problem. Given are a 1\times 1 1 × 1 square, a 2\times 2 2 × 2 square, and so on, finally a n\times n n × n square. What is the biggest square that can be covered completely by this given set of “small” 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 packing 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’s, the covering version of the problem seems new. We construct optimal coverings for small values of n . For moderately bigger n values we solve the problem optimally by a commercial mathematical programming solver, and for even bigger n 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 n , can generate a cover for a larger square using small squares up to size n+1 n + 1 . Finally we prove that a simple covering policy can generate an asymptotically optimal covering. | |
| 650 | 4 | |a Számítás- és információtudomány | |
| 700 | 0 | 1 | |a Dósa György |e aut |
| 700 | 0 | 1 | |a Hvattum Lars Magnus |e aut |
| 700 | 0 | 1 | |a Olaj Tomas Attila |e aut |
| 700 | 0 | 1 | |a Szalkai István |e aut |
| 700 | 0 | 1 | |a Tuza Zsolt |e aut |
| 856 | 4 | 0 | |u http://publicatio.bibl.u-szeged.hu/36974/7/s10479-025-06633-5.pdf |z Dokumentum-elérés |
| 856 | 4 | 0 | |u http://publicatio.bibl.u-szeged.hu/36974/1/Consecutive-squares-2024_04_05.pdf |z Dokumentum-elérés |