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.

A. Caprara, A. Lodi, S. Martello, M. Monaci (2006). Packing into the smallest square: Worst-case analysis of lower bounds. DISCRETE OPTIMIZATION, 3, 317-326 [10.1016/j.disopt.2006.06.001].

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.
2006
A. Caprara, A. Lodi, S. Martello, M. Monaci (2006). Packing into the smallest square: Worst-case analysis of lower bounds. DISCRETE OPTIMIZATION, 3, 317-326 [10.1016/j.disopt.2006.06.001].
A. Caprara; A. Lodi; S. Martello; M. Monaci
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.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11585/31057
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 5
  • ???jsp.display-item.citation.isi??? 5
social impact