On Three-Dimensional Packing

Abstract

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 \leqq r(G) \leqq 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_1 $ and $C_1 $, respectively, with $r(G_1 ) = 4$ and $r(C_1 ) = 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 (m \geqq 3)$ and $C^* _m (m \geqq 2)$, are presented. It is shown that $r(G^* _m ) = {m / {(m -2)}}$ and $r(C^* _m ) = {{(m+1)} / {(m-1)}}$. Similarly, when these small bottom boxes have square bottoms, there exist two families of algorithms, $G_m (m\geqq 2)$ and $C_m (m \geqq 2)$, such that $r(G_m )={(m / {(m-1)}})^2 $ and $r(C_m )=( {{(m+1)} / m} )^2 $.