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.
Packing into the smallest square: Worst-case analysis of lower bounds
CAPRARA, ALBERTO;LODI, ANDREA;MARTELLO, SILVANO;MONACI, MICHELE
2006
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.File in questo prodotto:
Eventuali allegati, non sono esposti
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
