Packing into the smallest square: Worst-case analysis of lower bounds

Packing into the smallest square: Worst-case analysis of lower bounds

0.00 Avg rating0 Votes
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: , , ,
Keywords: packing, geometry
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.

Reviews

Required fields are marked *. Your email address will not be published.