Multidimensional Cube Packing

We consider the \textit{$d$-dimensional cube packing problem} ({\rm {\it d}-CPP}): given a list $L$ of $d$-dim\-en\-sional cubes and (an unlimited quantity of) $d$-dimensional unit-capacity cubes, called \textit{bins}, find a packing of $L$ into the minimum number of bins. We present two approximation algorithms for {\rm {\it d}-CPP}, for fixed $d$. The first algorithm has an asymptotic performance bound that can be made arbitrarily close to~$2-(1/2)^d$. The second algorithm is an improvement of the first and has an asymptotic performance bound that can be made arbitrarily close to~$2-(2/3)^d$. To our knowledge, these results improve the bounds known so far for $d=2$ and $d=3$, and are the first results with bounds that are not exponential in the dimension.

2002