Article ID: | iaor20071438 |
Country: | Netherlands |
Volume: | 3 |
Issue: | 4 |
Start Page Number: | 317 |
End Page Number: | 326 |
Publication Date: | Dec 2006 |
Journal: | Discrete Optimization |
Authors: | Martello Silvano, Caprara Alberto, Lodi Andrea, Monaci Michele |
Keywords: | packing, geometry |
We address the problem of packing a given set of rectangles into the minimum size square. We consider three versions of the problem, arising when the rectangles (i) are squares; (ii) have a fixed orientation; (iii) can be rotated by 90°. For each case we study lower bounds, and analyze their worst-case performance ratio. In addition, we evaluate through computational experiments their average performance on instances from the literature.