aDEIS, Università di Bologna, Viale Risorgimento 2, I-40136 Bologna, Italy
bDEI, Università di Padova, Via Gradenigo 6/A, I-35131 Padova, Italy
Abstract:
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.