Content area
Abstract
A mail order firm receives an order from a customer for a few items in their catalog. These items must be packed in a box and shipped to the customer. To lower their shipping costs, the company wishes to pack the items in the smallest box possible. We examine this problem in the case of orthogonal packings where the items are rectangular bricks.
A box with dimensions $a\sb1 \times a\sb2 \times \cdot\cdot\cdot \times a\sb{k}$, encloses a brick with dimensions $b\sb1 \times b\sb2 \times \cdot\cdot\cdot \times b\sb{k}$, provided, $a\sb1 \geq b\sb1,a\sb2 \geq b\sb2,...,a\sb{k} \geq b\sb{k}$. Enclosure is a partial order on the set of all bricks. We show that the set of minimal elements, under this enclosure relation, of the boxes into which a given set of bricks can be packed, is finite.
We give an algorithm that produces these minimal boxes, in O((1 + $k\sp2)\sp{n}$) time, for the special case of cleave-packing. The problem of determining whether a given box can be cleave-packed by a given bricklist is NP-complete. Thus, the algorithm developed is about the fastest that can be expected.
When restricted to tower-packings, a nice combinatorial formula is given for the maximum number of minimal boxes for any n and k.
