@techreport{TR-IC-02-10,
number = {IC-02-10},
author = {Y. Kohayakawa and F. K. Miyazawa and
P.Raghavan and Y. Wakabayashi},
title = {Multidimensional Cube Packing},
month = {September},
year = {2002},
institution = {Institute of Computing, University of Campinas},
note = {In English, 15 pages.
\par\selectlanguage{english}\textbf{Abstract}
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.
}
}