K.~Hoffmann, G. Scheithauer
Relations between capacity utilization and minimal bin number
We consider the two-dimensional bin packing problem (BPP): given a set of rectangular items, find the minimal number of rectangular bins needed to pack all items. Rotation of the items is not permitted. We show if every item fits into the given bin and if the total area of the items to be packed does not exceed the area of the bin then at most three bins are needed to pack all items. Moreover, the bound three is tight. Furthermore, if the size parameters of all items are not larger than a third of that of the bin then only two bins are necessary to pack all items. (submitted Mai 2012)
PDF, (Preprint MATH-NM-03-2012, TU Dresden, May. 2012)