On Three-Dimensional Packing

The three-dimensional packing problem is discussed in this paper. The problem is a generalization of the one- and two-dimensional packing problems. It is demonstrated that some basic packing strategies such as NFDH and FFDH for two-dimensional packing have unbounded worst-case performance ratios in the three-dimensional case. Let $r(A)$ denote the asymptotic performance bound of an approximation algorithm A. An approximation algorithm G is developed, and it is shown that 4.333 r(G) 4.571. The algorithm is improved to algorithm C and it is proven that $r(C) = 3.25$. For the special case when all boxes have square bottoms, the two algorithms are adapted to algorithms G₁ and C₁, respectively, with r(G₁ ) = 4 and r(C₁ ) = 2.6875. For the case when both sides of the bottom of a box are no larger then 1 / m, two families of algorithms, G^* ₘ (m 3) and C^* ₘ (m 2), are presented. It is shown that r(G^* ₘ ) = m / (m -2) and r(C^* ₘ ) = (m+1) / (m-1). Similarly, when these small bottom boxes have square bottoms, there exist two families of algorithms, Gₘ (m 2) and Cₘ (m 2), such that r(Gₘ )=(m / (m-1))² and r(Cₘ )=( (m+1) / m )².