Abstract of Paper

Two dimensional packing: the power of rotation
by Leah Epstein


Recently there is a rise in the study of two dimensional packing problems.
In such problems the input items are rectangles which need to be assigned
into unit squares. However, most of the previous work concentrated on fixed
items. Fixed items have a fixed direction and must be assigned so that their
bottom is parallel to the bottom of the bin. In this paper we study two
dimensional bin packing of rotatable items.  Those are rectangles which can
be rotated by ninety degrees. We give almost tight bounds for bounded space
bin packing of rotatable items, and introduce a new unbounded space
algorithm. This improves the results of Fujita and Hada.