\documentclass[11pt]{article}
\usepackage{amscd}
\usepackage{amsfonts}
\usepackage{amsmath}
\usepackage{epsf}
\setlength{\textwidth}{39pc}
\setlength{\textheight}{56pc}
\setlength\oddsidemargin{0cm}  
\setlength\evensidemargin{0cm}  
\setlength{\topmargin}{0cm}
\setlength{\parskip}{0pc}
\setlength{\paperwidth}{216mm}
\setlength{\paperheight}{279mm}
\usepackage{doublespace} % To have a simple spaced text, comment this line

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\def\ykcomm#1{\footnote{\textsf{yk:} #1}}
\let\:=\colon
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\newcommand{\FFDS}{\rm FFDS}
\newcommand{\BbbZ}{\mathbb{Z}}
\newcommand{\BbbR}{\mathbb{R}}
\newcommand{\BbbP}{\mathbb{P}}
\newcommand{\bea}{\begin{eqnarray*}}
\newcommand{\eea}{\end{eqnarray*}}
\newcommand{\cala}{{\cal A}}
\newcommand{\cali}{{\cal I}}
\newcommand{\calo}{{\cal O}}
\newcommand{\calr}{{\cal R}}
\newcommand{\calsr}{{\cal SR}}
\newcommand{\calt}{{\cal T}}
\newcommand{\calu}{{\cal U}}
\newcommand{\opt}{{\rm OPT}}
\newcommand{\calp}{{\cal P}}
\newcommand{\hcalp}{\widehat{\cal P}}
\newcommand{\hhcalp}{{\widehat{\widehat{\cal P}}}}
\newcommand{\calq}{{\cal Q}}
\newcommand{\calb}{{\cal B}}
\newcommand{\dbpp}{{\rm {\it d}-BPP}}
\newcommand{\dcpp}{{\rm {\it d}-CPP}}
\def\proof{\noindent{\it Proof}. \ignorespaces}
\def\endproof{\hfill\vbox{\hrule height0.6pt\hbox{%
   \vrule height1.3ex width0.6pt\hskip0.8ex
   \vrule width0.6pt}\hrule height0.6pt
  }}
\newtheorem{theorem}{Theorem}[section]
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{example}[theorem]{Example}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{claim}[theorem]{Claim}
\newtheorem{observation}[theorem]{Observation}
\newtheorem{question}[theorem]{Question}
\newtheorem{problem}[theorem]{Problem}
%-------
\renewcommand{\thefootnote}{\fnsymbol{footnote}}\addtocounter{footnote}{1}

\bibliographystyle{plain}
%---------------------------------------------------------------------------

\title{Multidimensional Cube Packing\footnotemark[1]} 
\author{Y.~Kohayakawa\footnotemark[2] \and
        F.K.~Miyazawa\footnotemark[3] \and
        P.~Raghavan\footnotemark[4] \and
        Y.~Wakabayashi\footnotemark[2]}
      
%----------------------------------------------------------------
 
\begin{document}
%---------------------------------------------------------------------------
 \maketitle
\footnotetext[1]{This research was partially supported by 
MCT/CNPq under PRONEX project 107/97 and CNPq
  (Proc.~470608/01--3, 468516/00--0, 464114/00--4, 300334/93--1, 300301/98--7
  and~304527/89--0).}
\footnotetext[2]{Instituto de Matem\'atica e Estat\'{\i}stica ---
  Universidade de S\~ao Paulo. Rua do Mat\~ao, 1010 --- 05508--090 ---
  S\~ao Paulo--SP --- Brazil, \{yoshi,yw\}@ime.usp.br.}
\footnotetext[3]{Instituto de Computa\c{c}\~ao --- Universidade
      Estadual de Campinas, Caixa Postal 6176 --- 13084--971 ---
      Campinas--SP --- Brazil, fkm@ic.unicamp.br.}
\footnotetext[4]{Verity, Inc., 892 Ross Drive, Sunnyvale, CA 94089,
  USA, pragh@verity.com.}

   \begin{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.

      
      {\bf Key Words:} Approximation algorithms, multidimensional bin packing,
      asymptotic performance.
    \end{abstract} 

%---------------------------------------------------------------------------

\section{Introduction}

We consider a generalization of the one-dimensional bin packing
problem, called here {\it $d$-dimensional cube packing problem} ({\rm
  {\it d}-CPP}).  This is the following problem. Given a list $L$ of
$n$ $d$-dimensional cubes (possibly of different sizes) and $d$-dimensional
unit-capacity cubes, called {\it bins}, 
find an orthogonal packing of $L$ into the minimum number of bins. This
problem is in fact a special case of the \textit{$d$-dimensional bin
  packing problem} ({\rm {\it d}-BPP}), in which one has to pack
$d$-dimensional parallelepipeds into $d$-dimensional unit-capacity
bins.  Note that for $d=1$ these  problems coincide.

In 1989, Coppersmith and Raghavan \cite{CoppersmithR89} presented an online
algorithm for {\it d}-BPP with asymptotic performance bound $(3\cdot
2^d+1)/4$. This algorithm, when specialized to {\it d}-CPP, has asymptotic
performance bound $\left({3}/{2}\right)^d-\left({3}/{4}\right)^d+1$.
In~\cite{MiyazawaW00a}, Miyazawa and \mbox{Wakabayashi} presented
approximation algorithms for 3-CPP that can be generalized to $d$-CPP with
asymptotic performance bound $(4/3)^d-(8/9)^d+1$, which gives asymptotic
peformance bounds close to $1.99$ for $2$-CPP and $2.67$ for $3$-CPP.

The most studied case is when $d=1$.  For this case there are asymptotic
approximation schemes due to Karmarkar and Karp~\cite{KarmarkarK82} and
Fernandez de la Vega and Lueker~\cite{VegaL81}. For a recent survey on this
case, see Coffman, Garey and Johnson~\cite{CoffmanGJ97}.  For 2-BPP the
algorithm with the best asymptotic performance bound is due to Chung, Garey
and Johnson~\cite{ChungGJ82}, with bound $2.125$. For $3$-BPP Li and
Cheng~\cite{LiC90b} and Csirik and van Vliet~\cite{CsirikV93} designed
algorithms with asymptotic performance bound $4.84$. Their algorithms
generalize to $d$-BPP giving algorithms with asymptotic performance bound
close to $1.691^d$.  For a survey on approximation algorithms for packing
problems we refer to Coffman, Garey and Johnson~\cite{CoffmanGJ84}.

We present two approximation algorithms for {\rm {\it d}-CPP}. The
first algorithm has an asymptotic performance bound that can be made
as close to $2-(1/2)^d$ as desired.  The second algorithm is an
improvement of the first one and has an asymptotic performance bound
that can be made as close to $2-(2/3)^d$ as desired.  For $d=2$ and
$d=3$ the bounds are close to $14/9$ and $46/27$, respectively.  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.
%
Recently, Seiden and Stee \cite{SeidenS02} presented an algorithm for $d=2$
with bound $14/9+\epsilon$ that uses an idea similar to the one we present in
this paper.  It is most likely that the extended
abstract~\cite{KohayakawaMRW01}, where we announced a comparable result, with
explicit formulas for general~$d$ and full description of our algorithms, was
unknown to those authors.  %Complete proofs for the results announced
%in~\cite{KohayakawaMRW01} are given here.\ykcomm{nao sei se esta frase é
%  necessaria} 

The remainder of this paper is organized as follows. In the next
section we present the notation and some definitions.  In Section 3 we
describe restricted versions of $d$-CPP. In Section 4 we present our
approximation algorithms for $d$-CPP. We close with some open problems.

\section{Notation and definitions}

Given a cube $c$, the {\it size} of $c$, denoted by $s(c)$, is defined
as the length of an edge of $c$. If $L$ is a list of cubes, then we
denote by $V(L)$ the total {\it volume} of the cubes in $L$.  Throughout
this paper whenever we consider a list $L$ to be packed into unit bins
we suppose that all its cubes have size at most 1.

% We also denote by $V(c)$ the {\it volume} of $c$ and by%
% We denote by $|\mathcal{P}|$ the number of bins used in the packing
%$\mathcal{P}$. 

Given a list $L$ of cubes, and an algorithm $\mathcal{A}$, we denote
by $\mathcal{A}(L)$ the number of bins used by algorithm $\mathcal{A}$
when applied to~$L$, and by~${\rm OPT}(L)$ the number of bins used by
an optimal packing of $L$.  If $\calp$ is a packing of $L$, we denote
the number of bins used in $\calp$ by $|\calp|$.  Some of our
algorithms partition the input list $L$ into sublists $L_1,\ldots,L_k$
and then apply specialized algorithms for each sublist $L_i$
generating a partial packing $\calp_i$.  We denote the packing
obtained by the union of these packings by
$\calp_1\cup\ldots\cup\calp_k$.  We say that an algorithm
$\mathcal{A}$ has {\it asymptotic performance bound} $\alpha$ if there
exists a constant $\beta$ such that $\mathcal{A}(L) \leq \alpha \cdot
\opt(L) + \beta$ for all input lists~$L$.  If $\beta=0$, we also say
that $\alpha$ is an {\it absolute performance bound} for algorithm
$\mathcal{A}$.  We note that 2-CPP cannot be approximated within
$2-\epsilon$ in the absolute sense, unless $\textit{P}=\textit{NP}$
(see~\cite{FerreiraMW99}, where this result is deduced from~\cite{LeungTWYC90}).  
This and other negative results in terms of the absolute performance
bounds make the asymptotic performance analyses of approximation
algorithms for bin packing problems attractive.

\section{Restricted \dcpp}

Before considering the general problem, we present algorithms for
restricted instances of {\rm {\it d}-CPP}, to be used as subroutines. 

\subsection{Restricted sizes and types}
First, we consider instances that admit a constant upper bound $k$ on 
the number of different cube sizes and each cube size is at least
$\epsilon$. We denote the set of such instances  
by $\cali_{\epsilon,k,d}$.

In what follows we show that in this case an optimal solution can be
obtained in polynomial time by an enumeration process.

Given a list $L\in\cali_{\epsilon,k,d}$,
denote by $D(L)=(s_1,s_2,\ldots,s_k)$ the list of different sizes in
the list $L$ and by $M(L)=(m_1,m_2,\ldots,m_k)$ the list of the
multiplicities $m_i$ of the cubes with size $s_i$.


There are infinitely many ways of packing a list of cubes into a bin,
but the number of different configurations is bounded if we consider
only ``canonical'' packings. We say a packing $\calp$ is {\it canonical}
if no cube in $\calp$ can be shifted to a ``lower'' position in any
dimension, without overlapping cubes. Each configuration in a bin of a
canonical packing is called a {\it canonical pattern}. With this in
mind, we can compute all possible positions $\BbbP^d(L)$ in a bin
where a cube of $L$ can be packed. We set
$p(L):=\{p:=b_1s_1+b_2s_2+\cdots+b_ks_k: \ 0\leq
p\leq 1,\ 0\leq b_i\leq m_i\}$, and  define $\BbbP^d(L)$ as the set
$p(L)^d=p(L)\times \ldots\times p(L)$.

\begin{claim} For a given list $L$ in $\cali_{\epsilon,k,d}$, the
  cardinality of  $\BbbP^d(L)$ is bounded by a value that 
 depends only on $k$, $\epsilon$ and $d$.
\end{claim}
\begin{proof} 
  Since each cube of $L$ has size at least $\epsilon$, we have
  $b_i\leq \lfloor 1/\epsilon\rfloor $ for all $i$. Thus we can
  conclude that $(\lfloor 1/\epsilon\rfloor+1)^k$ is an upper bound on
  $p(L)$.  Therefore, we have $|\BbbP^d(L)|\leq (\lfloor
  1/\epsilon\rfloor +1)^{kd}$.
\end{proof}
\bigskip

For $L\in\cali_{\epsilon,k,d}$, let  $\rho_{\epsilon,k,d}(L)$ denote
the number of all possible canonical patterns of $L$.
The following result is immediate.
\begin{claim}
  The value $\rho_{\epsilon,k,d}(L)$ is bounded by a value that 
 depends only on $k$, $\epsilon$ and $d$.
\end{claim} 
\begin{proof} Note that the number of canonical patterns for $L$
  consisting of exactly $i$ cubes is bounded by
  $$
  k^i{|\BbbP^d(L)| \choose i}.
  $$
  Therefore,
  \bea 
  \rho_{\epsilon,k,d}(L) &\leq& k{|\BbbP^d(L)| \choose 1} + k^2{|\BbbP^d(L)| \choose
    2} + \cdots+
  k^{\epsilon^{-d}}{|\BbbP^d(L)| \choose \epsilon^{-d}},
  \eea
  and the result follows.
\end{proof}
\bigskip

%
%Let $P=(P_1,P_2,\ldots,P_w)$ be the set of all $w:=w_d(L)$ possible
%patterns, each pattern $P_i=(m_{i,1},m_{i,2},\ldots,m_{i,k})$ is
%represented as a $k$-dimensional vector where $m_{i,j}$ is the number
%of cubes $c_j$ packed into pattern $P_i$.
%
%The problem of finding a minimal solution for this restricted $d$-CPP
%problem can be formulated as the following integer linear programming
%problem.
%\[\begin{array}{ll}
% \min\sum x_i &   \\
%\mbox{s.a.} & P_1\cdot x_1+P_2\cdot x_2+\cdots +P_w\cdot x_w = M, \\
%& x_i\in \BbbZ^*
%\end{array}\]
%
%We will not solve this integer programming system, but a relaxed
%system with the last condition relaxed to $x_i\geq 0$.  We can find
%an optimum fractional solution $x^*\in \BbbR^d$ for this problem in
%polynomial time using at most $k$ patterns.  Rounding the
%fractional variables in $x^*$, we can obtain an asymptotic optimum
%solution for the restricted instance $L$. If we denote the above
%algorithm by $R_{\epsilon,k}$ the following result is valid.
%\begin{lemma}\label{lerek}
%If $L\in\cali_{\epsilon,k}$, then
%\[R_{\epsilon,k}(L)\leq \opt(L)+k,\]
%where $R_{\epsilon,k}$ runs in time $O(\tau_{k,\epsilon,d})$, where
%$\tau_{k,\epsilon,d}$ depends only on $k$, $\epsilon$ and $d$.
%\end{lemma}

Let $\calr_{\epsilon,k,d}$ denote the algorithm that generates all possible
canonical packings and chooses a packing using the smallest number of bins.

\begin{lemma}\label{lerek}
  Let $\epsilon$, $k$ and $d$ be fixed positive numbers and $L$ an instance of
  $d$-CPP with $L\in\cali_{\epsilon,k,d}$. Then $L$ can be packed optimally in
  polynomial time by the algorithm $\calr_{\epsilon,k,d}$.
%
%\[R_{\epsilon,k}(L)\leq \opt(L)+k,\]
%where $R_{\epsilon,k}$ runs in time $O(\tau_{k,\epsilon,d})$, where
%$\tau_{k,\epsilon,d}$ depends only on $k$, $\epsilon$ and $d$.
\end{lemma}
\begin{proof}
  Suppose $L$ has $n$ cubes. Since we can have at most $n$ bins of
  each pattern, the number of different packings is bounded by the
  polynomial $(n+1)^\rho$, where $\rho:=\rho_{\epsilon,k,d}(L)$.
\end{proof}
 
\subsection{Restricted size}
\label{sec:restricted_size}
In this section, we consider instances where we only have restriction on the
minimum size of a cube. We denote by $\cali_{\epsilon,d}$ the set of all
instances consisting of cubes with size greater than $\epsilon$.

We shall make use of the linear rounding technique presented by Fernandez de
la Vega and Lueker \cite{VegaL81} to obtain an asymptotic approximation scheme
$\calr_{\epsilon,d}$ for instances in $\cali_{\epsilon,d}$.

Given two instances $X$ and $Y$ for $d$-CPP, we write $X\preceq Y$ if there is
an injection $f\:X\rightarrow Y$ such that $s(c)\leq s(f(c))$ for all $c\in
X$.  Denote by $\overline{X}$ the instance with precisely $|X|$ cubes with
size equal to the size of the largest cube in $X$. Clearly, $X\preceq
\overline{X}$. The following claim is immediate.
\begin{claim}\label{factpreceq}
  If $X$ and $Y$ are two instances for $d$-CPP with $X\preceq Y$, then 
$\opt(X)\leq \opt(Y)$.
\end{claim}

We are now ready to describe the algorithm $\calr_{\epsilon,d}$.

\noindent
\begin{quote}{\noindent\sffamily
\textbf{Algorithm} $\calr_{\epsilon,d}(L)$

Input: $L\in \cali_{\epsilon,d}$

\begin{enumerate} 
  \setlength{\itemsep}{-1.3pt}
\item If~$L$ contains $<2/\epsilon^{d+1}$ cubes, find an optimal packing
  exhaustively and return this packing.  Otherwise, let $L=(c_1,\ldots,c_n)$
  be the input list sorted in non-increasing order of size.
\item Set $q:=\lfloor n\epsilon^{d+1}\rfloor$ and partition $L$ into
  groups $G_0,G_1,\ldots,G_k$ such that
  \begin{align}
    &G_0\succeq G_1\succeq \cdots \succeq G_k, \nonumber\\
    &\qquad\text{where $|G_i|=q$ for all~$i=0,\ldots,k-1$,} \nonumber\\
    &\qquad\text{and }|G_k|\leq q. \nonumber
  \end{align}
  
\item Let $\calp_0$ be the packing obtained by placing each
  cube of $G_0$ into a different bin
  %(or place the cubes in a same bin as long as possible). 
\item Let $J:=\bigcup_{i=1}^k G_i$ and $\widehat{J}:=\bigcup_{i=1}^k
  \overline{G}_i$. 
%That is
%  \[\begin{array}{llllllll}
%    L &=& G_0 & G_1 & G_2 & \ldots & G_{k-1} & G_k \vspace{4pt}\\
%    J &=&     &
%    \overline{G_1}&\overline{G_2}&\ldots&\overline{G_{k-1}}
%    &\overline{G_k}\vspace{4pt}\\ 
%    J'&=& G_0 & & & & & \\
%  \end{array}\]
\item Let ${\hcalp}$ be the packing of $\widehat{J}$ generated by the algorithm
$\calr_{\epsilon,k,d}$; and let $\calp_1$ be the packing of $J$
corresponding to $\widehat{J}$.
\item Return $\calp_0\cup \calp_1$.
\end{enumerate}}\end{quote}

\begin{lemma} \label{lerek2}
  For all input list $L\in\cali_{\epsilon,d}$, we have
 \bea
  \calr_{\epsilon,d}(L)\leq (1+\epsilon)\,\opt(L).
  \eea
Furthermore, $\calr_{\epsilon,d}$ is a polynomial time algorithm.
\end{lemma}
\begin{proof}
  It suffices to consider the case in which~$n\geq2/\epsilon^{d+1}$.  In step
  2 we partition the sorted list $L$ into $k+1$ groups $G_i$ each of which
  consists of $q=\lfloor n\epsilon^{d+1}\rfloor$ cubes, except perhaps for the
  last group, which may have fewer cubes.  Note that $k+1=\lceil
  n/\lfloor\epsilon^{d+1}n\rfloor\rceil\leq\lceil2/\epsilon^{d+1}\rceil$ and,
  therefore, the number of different cube types in list $\widehat{J}$ is
  bounded by a value that depends only on $\epsilon$ and $d$.  Since
  $\overline{G}_i\preceq G_{i-1}$ $(i=1,\ldots,k)$ we have $\widehat{J}\preceq
  L$. From Lemma \ref{lerek} and Claim \ref{factpreceq}, we have
  \begin{eqnarray}
  |\calp_1| =|{\hcalp}|=\opt(\widehat{J})\leq\opt(L). \label{eqr1}
  \end{eqnarray}
  The packing of $G_0$ uses at most $q$ bins, therefore
  \begin{equation}
    \label{eqr2}
    |\calp_0|\leq q=\lfloor n\epsilon^{d+1}\rfloor
    \leq n\epsilon^{d+1}
    \leq\epsilon\,V(L)
    \leq\epsilon\,\opt(L). 
  \end{equation}
%   \begin{eqnarray}
%    |\calp_0|  &\leq& q = \lfloor n
% \epsilon^{d+1}\rfloor\nonumber\\
%                     &\leq& n \epsilon^{d+1} \nonumber\\
%                     &\leq& \epsilon V(L)\nonumber\\
%                     &\leq& \epsilon \opt(L). \label{eqr2}
%   \end{eqnarray}
  From inequalities (\ref{eqr1}) and  (\ref{eqr2}), we have
  \begin{equation*}
    \calr_{\epsilon,d}(L)=|\calp_0| + |\calp_1| 
    \leq\opt(L)+\epsilon\,\opt(L) 
    \leq(1+\epsilon)\,\opt(L),
  \end{equation*}
  as required.
\end{proof}
\bigskip

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%% para quando \epsilon=1/3 %%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
We now turn to an algorithm that will be used only in the improved version of
our algorithm (see Section~\ref{sec:improved}).  This algorithm, which we
call~$\calr_{1/3,d}'$, is designed for the special case in which all
cubes have size greater than $1/3$ and is optimal.  We observe
that~$\calr_{1/3,d}'$ is a generalization for \dcpp\ of an algorithm
presented by Ferreira, Miyazawa and Wakabayashi~\cite{FerreiraMW99} for
$2$-CPP.

\noindent
\begin{quote}{\noindent\sffamily
{\bf Algorithm} $\calr_{1/3,d}'(L)$

Input: $L\in \cali_{1/3,d}$

\begin{enumerate}
    \setlength{\itemsep}{-1.3pt}
  \item Partition the list $L$ into the two sublists
    $$
L' :=\{c\in L:\ s(c)>1/2\} \qquad\text{and}\qquad
L'':= L\setminus L'.
    $$
%  \[\begin{array}{lll}
%    L' &:=& \{c\in L:\ s(c)> \frac{1}{2}\} \mbox{\ \ and}\\
%    L''&:=& L\setminus L'.
%  \end{array}\]
\item Sort the cubes in $L'$ in non-decreasing order of their sizes.
      Let $L'=(c_1', \ldots, c_{n'}')$.
\item Sort the cubes in  $L''$ in non-increasing order of their sizes.
      Let $L''=(c_1'', \ldots,c_{n''}'')$.
      \begin{itemize}
      \item[]We have
        $$
        {1\over3}<\dots\leq s(c_1'')\leq{1\over2}<s(c_1')\leq\cdots
        $$
      \end{itemize}
\item Call the subroutine $\calsr_{1/3,d}$ with parameters
      $(L',L'')$.

\begin{quote}
{\bf Subroutine} $\calsr_{1/3,d}(L',L'')$

\begin{enumerate}
    \setlength{\itemsep}{-1.3pt}
\item If $L'=\emptyset$ and $L''=\emptyset$ then return $\emptyset$;
\item else if $L'=\emptyset$ then generate a packing $\calp$ placing
the first $m:=\min\{2^d,n''\}$ cubes of $L''$ into one bin;
\item else if $L''=\emptyset$ then generate a packing $\calp$ placing 
the cube $c_1'$ into one bin;
\item else if $s(c_1')+s(c_1'')>1$ then generate a packing $\calp$
placing $m:=\min\{2^d,n''\}$ cubes of $L''$ into one bin;
\item else generate a packing $\calp$ placing the cube $c_1'$ and
$m:=\min\{2^d-1,n''\}$ cubes of $L''$ into one bin.
\item Remove from $L'$ and $L''$ the cubes that have been packed.
\item Return $\calp\cup\calsr_{1/3,d}(L',L'')$.
\end{enumerate}\end{quote}

\end{enumerate}}\end{quote}

First we prove that the packing generated by the algorithm $\calr_{1/3,d}'$ has
a very simple structure.  Indeed, we show that the bins generated by this
algorithm, except for possibly one, may have only three different
configurations.

\begin{lemma}\label{letipos}
  Let $L\in\cali_{1/3,d}$ be an instance for \dcpp{}, $L':=\{ c\in L : \;
  s(c)>\frac{1}{2}\;\}$ and $L'':= L\setminus L'$. Then the algorithm
  $\calr_{1/3,d}'$ applied to $L$ generates a packing where each bin, except
  for possibly one, has one of the following configurations.

\hspace*{1cm}$C1:$ configuration consisting of~$1$ cube of $L'$ and
$2^d-1$ cubes of $L''$.

\hspace*{1cm}$C2:$ configuration consisting of exactly~$1$ cube of
$L'$.

\hspace*{1cm}$C3:$ configuration consisting of $2^d$ cubes of $L''$.
\end{lemma}
\begin{proof}
  Note that each call of the subroutine $\calsr_{1/3,d}$ generates a one-bin
  packing and then packs the remaining cubes recursively. Let us then analyse
  steps~(b)--(e) of this subroutine, where a packing into one bin is
  generated.
  
  Clearly, the bin generated in step~(c) has configuration $C2$. In steps~(b),
  (d) and~(e), the bin that is generated does not have one of the three
  configurations only when the value of $m$ is $n''$ and $n''< 2^d$ (in
  steps~(b) and~(d)) or $n'' < 2^d-1$ (in step~(e)). But this happens only
  once, and after step~(f) we have $L''=\emptyset$ and therefore the next bins
  to be generated, if any, will have configuration~$C2$.
\end{proof}
%\bigskip

\begin{theorem}\label{teffds}
  The algorithm $\calr_{1/3,d}'$ finds an optimal solution for \dcpp{}
  restricted to instances $L\in\cali_{1/3,d}$ in polynomial time.
\end{theorem}
\begin{proof}
  The algorithm $\calr_{1/3,d}'$ partitions the list $L$ into two sublists
  $L'$ and $L''$, sorts them and calls the subroutine $\calsr_{1/3,d}$. In
  each call, this subroutine generates a one-bin packing and then packs the
  remaining cubes recursively.
  
  Consider a call of the subroutine $\calsr_{1/3,d}$ with parameters
  $(L',L'')$, and let $B$ be the bin generated in this call. We claim that
  there is an optimal packing $\calp^*$ of $L'\cup L''$ that has a bin $B^*$
  with the same cubes as~$B$.  This is clearly true if the packing of the bin
  $B$ is generated in steps~(a), (b), or~(c).  (For step~(b), it is crucial
  that the cubes have size greater than~$1/3$.)
  
  Now suppose that~$B$ is generated in step~(d).  In this case,
  the largest cube $c_1''$ of $L''$ cannot be packed with the smallest
  cube of $L'$.  Therefore, any optimal packing $\calp^*$ does not have
  $c_1''$ with any other cube in $L'$.  Let $B^*$ be the bin of
  $\calp^*$ containing the cube $c_1''$. Since $B$ contains the
  largest cubes of $L''$, we can exchange the cubes of $B^*$, so that
  it ends up with the cubes packed in $B$.  In fact, if $c\in B\setminus
  B^*$ and $C^*$ is the bin of $\calp^*$ containing $c$, then we
  can clearly exchange any cube in $B^*\setminus B$ with cube $c$.
  Repeating this process, we obtain an optimal packing that has  a
  bin containing the same cubes as~$B$.
  
  The proof for the case in which~$B$ is generated in step~(e) is analogous.
  The result follows by induction.
\end{proof}
\bigskip


\section{Approximation algorithms for \dcpp}

In this section we present two approximation algorithms for
$d$-CPP. The first has asymptotic performance bound that can be made
as close to $2-(1/2)^d$ as desired and the second has asymptotic
performance bound that can be made as close to  $2-(2/3)^d$ as
desired.

Both algorithms use the NFDH (Next Fit Decreasing Height) algorithm as a
subroutine, to be described in what follows.

The algorithm ${\rm NFDH}$ generates $t$-dimensional strips (using dimensions
$1,\ldots,t$) using $(t-1)$-dimensional strips (dimensions $1,\ldots,t-1$)
which are packed in non-increasing order of their size (the size of a strip is
the size of the largest cube in it).  The $(t-1)$-dimensional strips are
packed side by side in dimension $t$ until a $(t-1)$-dimensional strip cannot
be packed (the sum of the $(t-1)$-dimensional strip sizes cannot be greater
than $1$).  In this case, the $(t-1)$-dimensional strip starts a new
$t$-dimensional strip.  The $0$-dimensional strips are the cubes themselves
and the $d$-dimensional strips are the packings generated into bins.
For more details of NFDH, see~\cite{MeirM68}.

The following result was proved by Meir and Moser \cite{MeirM68} for the
algorithm NFDH. We can derive from it two corollaries which will be
useful to prove the bounds for our algorithms.

\begin{theorem}\label{teMeirM68} Let $L$ be a list of $d$-dimensional
  cubes with  maximum size $s$. Then $L$ can be packed by the algorithm
  NFDH into a $d$-dimensional $a_1\times a_2\times\cdots\times a_d$
  parallelepiped if
  \[V(L)\leq s^d+(a_1-s)(a_2-s)\cdots(a_d-s).\]
\end{theorem}

\begin{corollary}\label{coro1}
  Let $\calp$ be the packing into unit bins obtained by applying the algorithm
  NFDH to a list $L$ consisting of $d$-dimensional cubes with maximum size
  $\epsilon$.  Then each sublist of cubes packed in a bin used by $\calp$,
  except for possibly one, has volume greater than $(1-\epsilon)^d$.
\end{corollary} 
\begin{proof}
  Suppose~$\calp$ uses~$m$ bins, and let $L_i=(c_1^i,\ldots,c_{n_i}^i)$ be the
  sublist packed in the $i$-th bin.  Since the set $L_i\cup \{c_1^{i+1}\}$,
  for $1\leq i\leq m-1$, could not be packed by the algorithm NFDH in the
  $i$-th bin, we have $V(L_i\cup \{c_1^{i+1}\})>\epsilon^d+(1-\epsilon)^d$.
  Therefore,
  \[
  V(L_i) > \epsilon^d+(1-\epsilon)^d-V(c_1^{i+1})\geq (1-\epsilon)^d
  \]
  for~$i=1,\dots,m-1$.
 \end{proof}

 \begin{corollary}\label{coro2}
   Let $\calp$ be the packing into unit bins obtained by applying the
   algorithm NFDH to a list $L$ of $d$-dimensional cubes.  Then each sublist
   of cubes packed in a bin used by $\calp$, except for possibly one, has
   volume at least $(1/2)^d$.
\end{corollary}

\begin{proof}
Clearly, it suffices to analyse the sublists (packed in a bin)
containing cubes with size at most $1/2$. Consider then a list
consisting of these sublists. Applying Corollary~\ref{coro1} to this
list the result is immediate. 
\end{proof}

\medskip

%%%%% new

We now state a technical lemma~\cite{MiyazawaW0xx} that will be useful in the
proofs of Theorems~\ref{telinha} and \ref{teoprincipal}.


\begin{lemma} \label{lemma_max}
 Suppose  $a,b,\gamma,\delta$ are real numbers such that $a>0$ and $0<\gamma<\delta<1$.
 Then
 $$\frac{a+b}{\max\{a,\,  \gamma a + \delta b\}}\leq 1+ \frac{1-\gamma}{\delta}.$$
 \end{lemma}

\medskip


\subsection{First Algorithm}
Now we are ready to describe the first algorithm of this section, called
$\cala_{\epsilon,d}'$, which depends on a parameter $\epsilon$. This parameter is used to
subdivide the list $L$ into two sublists: one consisting of ``large'' cubes
(size greater than $\epsilon$) and the other consisting of ``small'' cubes.
For the large cubes we use the asymptotic approximation scheme presented in
Section~\ref{sec:restricted_size}, and for the small cubes we use the
algorithm NFDH. In order to obtain bounds for the volume of the large cubes we
also use the algorithm NFDH.

\begin{quote}{\noindent\sffamily
Algorithm $\cala_{\epsilon,d}'(L)$
\begin{enumerate}
\setlength{\itemsep}{-1.3pt}
\item Partition the list $L$ into the two sublists
$$
L' := \{c\in L:\ s(c)> \epsilon\} \qquad\text{and}\qquad
L'':= L\setminus L'.
$$
%  \[\begin{array}{lll}
%    L' &:=& \{c\in L:\ s(c)> \epsilon\} \mbox{\ \ and}\\
%    L''&:=& L\setminus L'.
%  \end{array}\]
\item Generate a packing $\calp_1'$ of $L'$ using the algorithm
  $\calr_{\epsilon,d}$.
\item Generate a packing $\calp_2'$ of $L'$ using the algorithm
  NFDH.
\item Let $\calp'$ be a packing in $\{\calp_1',\calp_2'\}$ that uses
  the least number of bins.
\item Generate a packing $\calp''$ of $L''$ using algorithm NFDH.
\item Return $\calp' \cup \calp''$.
\end{enumerate}}\end{quote}

\begin{theorem}\label{telinha}
  For fixed values of $d$ and $\epsilon$ the algorithm
  $\cala_{\epsilon,d}'$ runs in polynomial time. Furthermore, we have 
  \[
  \cala_{\epsilon,d}'(L)\leq \alpha^{}_{\epsilon,d} \opt(L)+2,
  \]
  where $\alpha^{}_{\epsilon,d}\to2-(1/2)^d$ as $\epsilon\rightarrow 0$.
\end{theorem}
\begin{proof}
  Since the algorithms $\calr_{\epsilon,d}$ and NFDH are polynomial time
  algorithms, $\cala_{\epsilon,d}'$ is also a polynomial time
  algorithm.  Let us analyse the performance of~$\cala_{\epsilon,d}'$.  

Let $n':=|\calp'|-1$ and $n'':=|\calp''|-1$. 
>From steps 3 and 4 and Corollary \ref{coro2}, we have
\begin{equation}
  \label{eqlinha} 
V(L') \geq \frac{1}{2^d}(|\calp_2'|-1)
      \geq \frac{1}{2^d}(|\calp'|-1)
      \geq \frac{1}{2^d}n'.  
\end{equation}
>From step 5 and Corollary \ref{coro1}, we have
\begin{equation}
  \label{eqduaslinhas} 
  V(L'') \geq (1-\epsilon)^d(|\calp''|-1)
  \geq  (1-\epsilon)^dn''. 
\end{equation}

>From inequalities (\ref{eqlinha}) and (\ref{eqduaslinhas}) and the
fact that the volume  
of the cubes in $L$ is a lower bound for the optimum packing, we
conclude that 
\begin{equation}
  \label{eq5}
  \opt(L) \geq V(L)
          = V(L')+V(L'')
          \geq \frac{1}{2^d}n' + (1-\epsilon)^d n''.
\end{equation}
The packing $\calp_1'$ of sublist $L'$ is generated by an asymptotic
approximation scheme (see Lemma~\ref{lerek2}). Since from step 4 the packing
$\calp'$ of $L'$ is such that $|\calp'|\leq |\calp_1'|$, we have
\begin{equation}
  \label{eq6}
\opt(L) \geq \opt(L') 
        \geq \frac{1}{1+\epsilon}\,|\calp'|
        \geq  \frac{n'}{1+\epsilon}.
\end{equation}

>From inequalities (\ref{eq5}) and (\ref{eq6}), we have
\begin{equation}
  \label{eq:OPT_lwbd}
  \opt(L)
  \geq
  \max\left\{\frac{n'}{1+\epsilon},\frac{1}{2^d}n'+(1-\epsilon)^dn''\right\}.
\end{equation}

Since $\cala_{\epsilon,d}'(L)=|\calp'|+|\calp''|$, we obtain 
\bea
\cala_{\epsilon,d}'(L) &=& (n'+1)+(n''+1) \\
                &=& \frac{n'+n''}{\opt(L)} \opt(L)+2\\
%                &\leq&
%                \frac{n'+n''}{\max\{\frac{n'}{1+\epsilon},
%                  \frac{1}{2^d}n'+(1-\epsilon)^dn''\}} \opt(L)+2 \\ 
                &\leq&\alpha^{}_{\epsilon,d}\opt(L)+2,
\eea
%
where $\alpha^{}_{\epsilon,d}=({n'+n''})/({\max\{{n'}/({1+\epsilon}),
  ({1}/{2^d})n'+(1-\epsilon)^d n''\}})$ (see~\eqref{eq:OPT_lwbd}).  From
Lemma~\ref{lemma_max}, we conclude that $\lim_{\epsilon\rightarrow
  0}\alpha^{}_{\epsilon,d}\leq 2-(1/2)^d.$
\end{proof}
%\bigskip

\begin{proposition}\label{proptight}
The asymptotic performance bound $2-(1/2)^d$  of the algorithm
$\cala_{\epsilon,d}'$ is tight.
\end{proposition}
\begin{proof}
  Let $L'$ be a list of $n'$ cubes of size $1/2+\xi$, where $n'$ is a
  large integer and $\xi$ is a small real such that  $\xi<\epsilon$ and 
  $1/\xi$ is an integer.  Let $L''$ be a list of $n'':=\lceil (1-1/2^d)
  n' \rceil/\xi^d$ cubes of size $\xi$.
  
  Consider a packing $\calp$ of a list $L:=L'\cup L''$ generated by the
  algorithm $\cala_{\epsilon,d}'$.  The algorithm $\cala_{\epsilon,d}'$ packs
  $L'$ and $L''$ separately. For $L'$ the algorithm uses at least $n'$ bins.
  For $L''$, the algorithm generates a packing using
  $\lceil(1-(1/2)^d)n'\rceil$ bins. That is, $\cala_{\epsilon,d}'(L)=
  n'+\lceil(1-(1/2)^d)n'\rceil$.
  
  On the other hand, an optimal packing of $L$ can be found using $n'+1$ bins.
  Therefore, the ratio $\cala_{\epsilon,d}'(L)/\opt(L)$ can be made as close
  to $2-({1}/{2})^d$ as desired.
\end{proof}

\subsection{Improved Algorithm}
\label{sec:improved}

In this section we present an algorithm that is an improvement
of~$\cala_{\epsilon,d}'$. This algorithm has an asymptotic performance bound
that can be made as close to $2-(2/3)^d$ as desired. We call this algorithm
$\cala_{\epsilon,d}$.

In the previous section we presented an algorithm that partitions the input
list $L$ into two sublists $L'$ and $L''$ and generates a packing consisting
of two parts.  Part (i), for the list $L'$ (of the cubes with size greater
than $\epsilon$), consists of an almost optimal packing but possibly with a
poor bound for the volume occupation in each bin.  Part (ii), for the list
$L''$ (of the cubes with size at most $\epsilon$), consists of a packing with
a good bound for the volume occupation.

The algorithm $\cala_{\epsilon,d}$ uses the small cubes of part (ii) to fill
the bins of part (i) with poor volume occupation. Since these bins may have
very complex item allocation we first reorganize the bins with very poor
volume occupation in such a way as to have a packing with a more tractable
configuration. After this reorganization and the packing of small items, we
have one of the following two situations.  \textit{Either} we have packed all
the small cubes into bins of part (i), \textit{or else} we were not able to
pack all the small cubes in the non-occupied space of the bins in part (i).

As we shall see, in the first case, we generate an almost optimal packing.  In
the second case, we obtain a better volume bound for the (newly generated)
bins of part (i) and this leads us to an improvement of the final bound.


Let us describe the main steps of the algorithm.  In step 1 we subdivide the
input list into two sublists, $L'$ and $L''$, as in the previous algorithm. In
step 2 we use an asymptotic approximation scheme to obtain a packing $\calp'$
for the sublist $L'$. In step 3 we separate the bins of $\calp'$ with poor
volume occupation and in step 4 we reorganize these bins so as to get all
bins, except for perhaps one, with good volume occupation, or bins with only
one large cube and poor volume occupation. In step 5 we pack the small cubes
of sublist $L''$ into the remaining space of the bins with only one large
cube.
%More details of some steps are described in the proof of the next
%theorem. 


\begin{quote}{\noindent\sffamily
Algorithm $\cala_{\epsilon,d}(L)$

\begin{description}
   \setlength{\itemsep}{-1.3pt}
   \item[\rm 1.] Partition the list $L$ into the two sublists
$$
L' := \{c\in L:\ s(c)> \epsilon\} \qquad\text{and}\qquad
L'':= L\setminus L'.
$$
%      \[\begin{array}{lll}
%      L' &:=& \{c\in L:\ s(c)> \epsilon\} \mbox{\ \ and}\\
%      L''&:=& L\setminus L'.
%      \end{array}\]
    \item[\rm 2.] Generate a packing $\calp'$ of the sublist $L'$ using
      algorithm $\calr_{\epsilon,d}$.
    \item[\rm 3.] Let $\calp_1'$ consist of all bins of packing $\calp'$ with
      volume occupation less than $(2/3)^d$, and let $\calp_2'$ consist of the
      remaining bins of $\calp'$. Let $L_1'$ be the cubes in $\calp_1'$.
   \item[\rm 4.] Generate a new packing ${\hcalp_1'}$ of $L_1'$ as
follows
       \begin{description}
          \setlength{\itemsep}{-1.3pt}
       \item[\rm 4.1] Let $S_i:=\{c\in L_1':\
         s(c)\in\left(\frac{1}{i+1},\frac{1}{i}\right]\}$, for
         $i=1,\ldots,8$ and\\
         let $S_9:=\{c\in L_1':\
s(c)\leq \frac{1}{9}\}$.
       \item[\rm 4.2] Generate a packing $\calp_{12}$ of $S_1\cup S_2$
   using the algorithm $\calr_{1/3,d}'$, and let $\calu$ be the
   set of bins in $\calp_{12}$ with configuration $C2$.
       \item[\rm 4.3] For $i=3,\ldots,8$, repeat the following steps
          \begin{description}
            \setlength{\itemsep}{-1.3pt}
          \item[\rm 4.3.1] If $\calu$ is empty, pack (up to) $i^d$ cubes
            of $S_i$ in a new bin $B$.
          \item[\rm 4.3.2] If $\calu$ is not empty then \\
            \hspace*{8mm}Let $B$ be a bin in $\calu$;\\
            \hspace*{8mm}If $i\in\{3,4,5\}$ then let $m:=i^d-(i-1)^d$ else let $m:=i^d-(i-2)^d$;\\
            \hspace*{8mm}Pack (up to)  $m$ cubes of $S_i$ (around the
            unique cube in $B$); \\  
            \hspace*{8mm}Update  $S_i$;\\
            \hspace*{8mm}Remove $B$ from $\calu$.
         \end{description}
       \item[\rm 4.4] Pack the cubes in $S_9$, as follows
         \begin{description}
           \setlength{\itemsep}{-1.3pt}
          \item[\rm 4.4.1] Subdivide the empty space of each bin $B\in
            \calu$ (around the unique cube in $B$) into
            $3^d-2^d$ smaller bins with size $1 /3$. Let $\calu'$ be
            the set of these smaller bins. 
          \item[\rm 4.4.2] Pack the cubes of $S_9$ into
            bins of $\calu'$ using the algorithm NFDH. Remove the used
   bins of $\calu'$. Use new unit bins
            if necessary.
            \end{description}
      \end{description}
   \item[\rm 5.] Pack the cubes of $L''$ into bins $\calu'$ using the
   algorithm NFDH. Use new unit bins if necessary.
   \item[\rm 6.] Return the generated packing $\calp$.
\end{description}}\end{quote}



\begin{theorem}\label{teoprincipal}
  For fixed values of $d$ and $\epsilon$ the algorithm $\cala_{\epsilon,d}$
  runs in polynomial time.  Furthermore, we have
  \[\cala_{\epsilon,d}(L)\leq \alpha^{}_{\epsilon,d} \opt(L)+9,\] 
  where $\alpha^{}_{\epsilon,d}\to2-(2/3)^d$ as $\epsilon\rightarrow 0$.
\end{theorem}
\begin{proof}
  From steps 2 and 3 and Lemma \ref{lerek2}, we have 
  \begin{equation}\label{eqte21}
    |\calp_1'|+|\calp_2'|=|\calp'|\leq (1+\epsilon) \opt(L),
  \end{equation}
  where $\calp_1'$ consists of the bins of $\calp'$ with volume occupation
  less than $(2/3)^d$.
  
  In step 4, the packing $\calp_1'$ of $L_1'$ is reorganized in such a way
  that all bins with volume occupation less than $(2/3)^d$ will end up with
  volume occupation at least~$(2/3)^d$.
%  , except for perhaps
%  one, have exactly one cube of size greater than $1/2$.

  In step 4.2 the algorithm $\calr_{1/3,d}'$ generates
  an optimal packing $\calp_{12}$ of $S_1\cup S_2$ which contains bins
  with configurations $C1$, $C2$ or $C3$,  described in Lemma
  \ref{letipos}.
  
  The bins of $\calp_{12}$ with configuration $C1$ (containing 1 cube
  with volume at least $1/2^d$ and $2^d-1$ cubes with volume at least
  $1/3^d$) have volume occupation at least $1/2^d+(2^d-1) 1/3^d$,
  which is greater than $(2/3)^d$. The bins of $\calp_{12}$ with
  configuration $C3$ (containing $2^d$ cubes with volume at least
  $1/3^d$) have volume occupation at least $(2/3)^d$.
  
  Therefore, the only bins of $\calp_{12}$ with volume occupation less than
  $(2/3)^d$ are the bins with configuration $C2$. These are exactly the bins
  $\calu$ taken in step 4.2.  Note that any bin with configuration $C2$ has
  exactly one cube with size less than $2/3$ and therefore we have space for
  packing smaller cubes around it.  The packing of the remaining cubes of
  $L_1'$ into these spaces is accomplished in steps 4.3 and 4.4. Moreover, we
  show that, after these steps, the only bins with volume occupation less than
  $(2/3)^d$ that could remain have configuration $C2$, except perhaps for a
  constant number of bins.
  
  We prove the previous statement considering the packing of each sublist
  $S_i$, $i=3,\ldots,8$. First, let us consider the packing of the cubes in
  $S_3$.  Suppose that $\calu$ contains at least one bin $B$. In this case, we
  can pack at least $3^d-(3-1)^d$ cubes around the unique cube in $B$. This is
  possible because each cube of $S_3$ has size at most $1/3$ and the cube
  in~$B$ has size at most $2/3$.  Since each cube of $S_3$ has volume at least
  $1/4^d$ and the cube in $B$ has volume at least $1/2^d$, the bins
  $B\in\calu$ after receiving the cubes of $S_3$ will have volume occupation
  \[
  V_{oc}(B) \geq \frac{1}{2^d}+(3^d-2^d) \frac{1}{4^d}
  \geq \left(\frac{2}{3}\right)^d.
  \]
  This holds for all such bins $B$, except perhaps for the last one.  If
  during the packing of cubes in $S_3$ the set $\calu$ becomes empty, then the
  algorithm packs the remaining cubes of $S_3$ by placing $3^d$ cubes in each
  new unit bin. In this case, each bin $B$ of this type has volume occupation
  \[
  V_{oc}(B) \geq 3^d\frac{1}{4^d}\geq \left(\frac{2}{3}\right)^d,
  \]
  except perhaps for the last one.
       
  The analysis for the packing of the sublists $S_4,\ldots,S_8$ is analogous.
  We can prove a volume occupation of $(2/3)^d$ for each rearranged bin of
  $\calu$, except perhaps for one bin in each of these sublists.  For the new
  bins we can also guarantee the same volume occupation.
  
  Let us consider the packing of the cubes in $S_9$ into the remaining
  bins of $\calu$. Suppose there is a bin $B$ in $\calu$. Since the
  unique cube placed (so far) in $B$ has size at most $2/3$, we can
  partition the empty space inside $B$ into $3^d-2^d$ smaller bins of
  size $1/3$. The set of these small bins is denoted by 
  $\calu'$, and in step 4.4.2 the algorithm NFDH is used to pack the
  cubes of $S_9$ into these bins (inside $B$). From Corollary
  \ref{coro1}, the algorithm NFDH generates packings into bins $B'\in
  \calu'$ with volume occupation at least $(1/3-1/9)^d$. Since we have
  $3^d-2^d$ bins of $\calu'$ inside each bin $B$ of $\calu$, the 
   bins $B$ after being filled  with cubes of $S_9$ will have a volume
  occupation
  \begin{equation*}
    V_{oc}(B)\geq\frac{1}{2^d}+(3^d-2^d)
    \left(\frac{1}{3}-\frac{1}{9}\right)^d\\ 
    \geq\frac{1}{2^d}+\frac{2^d}{3^d}-\frac{4^d}{9^d}\\
    >\left(\frac{2}{3}\right)^d.
  \end{equation*}
  If during the packing of cubes in $S_9$ the set $\calu'$ becomes
  empty, then the algorithm packs the remaining cubes of $S_9$ into
  new unit bins. From Corollary \ref{coro1}, each bin $B$ of this type
  has volume occupation
  \[V_{oc}(B) > \left(1-\frac{1}{9}\right)^d 
  > \left(\frac{2}{3}\right)^d.\] 
       
  From the previous inequalities, we can conclude that, after step 4, the
  only bins in $\calu$ which have volume occupation less than $(2/3)^d$
  are the remaining bins of configuration $C2$, except perhaps for 8 bins
  (one for each sublist $S_i$, $i=2,\ldots,9$).
  %Moreover, the empty space in each bin of
  %configuration $C2$ is partitioned into $3^d-2^d$ small bins with
  %size $1/3$. The set of all these remaining smaller bins is denoted
  %by the set $\calu'$. 

  At this point, we can conclude the following: If all cubes of
  $S_3,\ldots,S_9$ were packed inside bins of $\calu$, then the
  packing ${\hcalp_1'}$ does not use more bins than the optimal
  packing $\calp_{12}$, and therefore the packing ${\hcalp_1'}$ is
  also optimal. That is
  \begin{equation}\label{igual}
  |{\hcalp_1'}|\leq |\calp_1'|.
  \end{equation}
  If the set $\calu$ becomes empty in some iteration, we have obtained a
  packing of $L_1'$ with volume occupation of at least $(2/3)^d$ in each bin,
  except perhaps for the last. Since the bins of the packing $\calp_1'$ have
  volume occupation less than $(2/3)^d$, we can conclude that the packing
  ${\hcalp_1'}$ has at most 8 bins more than the packing $\calp_1'$.
  That is,
 \begin{equation}\label{igual2}
  |{\hcalp_1'}|\leq|\calp_1'|+8.
  \end{equation}
  From inequalities (\ref{igual}), (\ref{igual2}) and (\ref{eqte21}), we
  have
  \begin{equation}\label{eqopt1}
   |{\hcalp_1'}|+|\calp_2'|\leq (1+\epsilon) \opt(L)+8.
  \end{equation}
  
  At last, we have to consider the packing of the cubes in $L''$
  generated in step 5. The cubes of this sublist is first packed by
  the algorithm NFDH into the remaining bins of $\calu'$, which are
  inside the bins of ${\hcalp_1'}$ with configuration $C2$. If
  necessary, new unit bins are used. The analysis of this step is
  divided into two cases:
  \begin{description}
%    \setlength{\itemsep}{-1.3pt}
  \item[\it Case 1.] All cubes of $L''$ have been placed
  inside the bins of $\calu'$. In this case, we have not used any new
  unit bin and, therefore, 
  \begin{equation}\label{eqfinal1}
   |\calp| = |{\hcalp_1'}|+|\calp_2'|\leq (1+\epsilon) \opt(L)+8.
  \end{equation}
 
 \item[\it Case 2.] New unit bins have been used in the packing of
  $L''$. In this case, each bin $B$ of $\calu$ has been ``filled''
  with cubes in $L''$. From Corollary \ref{coro1}, the bin $B$ 
  has volume occupation
  \[V_{oc}(B) > \left(1-\epsilon\right)^d 
  > \left(\frac{2}{3}\right)^d.\] 
  %for suficiently small values of $\epsilon$. 
  Let $\widehat{\widehat{\calp_1'}}$ be the packing ${\hcalp_1'}$ with
  the bins of configuration $C2$ filled with cubes of $L''$, and
  ${\hcalp''}$ be the packing of the remaining cubes in $L''$ into new
  unit bins. Denote the set of cubes packed in ${\hcalp''}$ as
  $\widehat{L''}$. Since the packing $\widehat{\widehat{\calp_1'}}$ and the
  packing ${\hcalp_1'}$ have the same number of bins and the packing
  $\calp_1'$ is an asymptotically optimal packing, the packing
  $\widehat{\widehat{\calp_1'}}$ is also an asymptotically optimal packing.
  
  Now, the final packing $\calp$ consists of two parts: an almost 
  asymptotically optimal packing $\widehat{\widehat{\calp_1'}}\cup \calp_2'$,
  \[|\widehat{\widehat{\calp_1'}}\cup \calp_2'|\leq (1+\epsilon)
  \opt(L)+8,\]
  with volume occupation of $(2/3)^d$ in each bin, except perhaps in 9
  bins; and the packing ${\hcalp''}$ containing the remaining 
  cubes of $L''$ into unit bins. From Corollary \ref{coro1}, we have
  \[
  |{\hcalp''}|\leq{1\over(1-\epsilon)^d}V(\widehat{L''})+1.
  \]
  Proceeding as in the proof of Theorem \ref{telinha}, we may conclude that 
  \[
  \cala_{\epsilon,d}(L)\leq \alpha^{}_{\epsilon,d} \opt(L)+9,
  \] 
  where $\alpha^{}_{\epsilon,d}=(n'+n'')/
  {\max\{1/(1+\epsilon)n',(2/3)^dn'+(1-\epsilon)^dn''\}}$. 
  From Lemma~\ref{lemma_max}, we have $\lim_{\epsilon\rightarrow 0}\alpha^{}_{\epsilon,d}\leq 2-(2/3)^d.$
\end{description}
Finally, note that all steps of the algorithm
$\cala_{\epsilon,d}$ can be implemented to 
run in polynomial time.
\end{proof}
%\bigskip

\begin{proposition}
The asymptotic performance bound $2-(2/3)^d$  of algorithm
$\cala_{\epsilon,d}$ is tight.
\end{proposition}
\begin{proof}
  The proof of this result is similar to the proof of Proposition
  \ref{proptight}.  Consider a list $L:=L'\cup L''$, such that $L'$ has
  $n'$ cubes of size $2/3+\xi$ and $L''$ has $n'':=\lceil(1-(2/3)^d) n'\rceil /\xi^d$
  cubes of size $\xi$, where~$n'$ is a large integer and~$\xi$ is a small
  real; we omit the details. 
\end{proof}
\bigskip

\section{Open problems}
We believe the following problems should be tackled.

\begin{problem} Is there an asymptotic approximation scheme
  for $d$-CPP?
\end{problem}

\begin{problem}
  Prove better bounds of inapproximability in the absolute sense for the
  $d$-dimensional case.
\end{problem}

%\bibliography{packing}  % The bibtex file can be obtained in 
                        % http://www.ic.unicamp.br/~fkm/packing.bib
\begin{thebibliography}{10}

\bibitem{ChungGJ82}
F.~R.~K. Chung, M.~R. Garey, and D.~S. Johnson.
\newblock On packing two-dimensional bins.
\newblock {\em SIAM Journal on Algebraic and Discrete Methods}, 3:66--76, 1982.

\bibitem{CoffmanGJ84}
E.~G. {Coffman, Jr.}, M.~R. Garey, and D.~S. Johnson.
\newblock Approximation algorithms for bin packing - an updated survey.
\newblock In G.~Ausiello, M.~Lucertini, and P.~Serafini, editors, {\em
  Algorithms design for computer system design}, pages 49--106. Spring-Verlag,
  New York, 1984.

\bibitem{CoffmanGJ97}
E.~G. {Coffman, Jr.}, M.~R. Garey, and D.~S. Johnson.
\newblock {\em Approximation algorithms (ed. D. Hochbaum)}, chapter
  Approximation algorithms for bin packing - a survey.
\newblock PWS, 1997.

\bibitem{CoppersmithR89}
D.~Coppersmith and P.~Raghavan.
\newblock Multidimensional on-line bin packing: algorithms and worst-case
  analysis.
\newblock {\em Operations Research Letters}, 8(1):17--20, 1989.

\bibitem{CsirikV93}
J.~Csirik and A.~{van Vliet}.
\newblock An on-line algorithm for multidimensional bin packing.
\newblock {\em Operations Research Letters}, 13:149--158, 1993.

\bibitem{VegaL81}
W.~{Fernandez de la Vega} and G.~S. Lueker.
\newblock Bin packing can be solved within $1+\epsilon $ in linear time.
\newblock {\em Combinatorica}, 1(4):349--355, 1981.

\bibitem{FerreiraMW99}
C.~E. Ferreira, F.~K. Miyazawa, and Y.~Wakabayashi.
\newblock Packing of squares into squares.
\newblock {\em Pesquisa Operacional}, 19(2):223--237, 1999.

\bibitem{KarmarkarK82}
N.~Karmarkar and R.~M. Karp.
\newblock An efficient approximation scheme for the one dimensional bin packing
  problem.
\newblock In {\em Proc. 23rd Ann. Symp. on Foundations of Computer Science},
  pages 312--320, Los Angeles, 1982. IEEE Computer Society.

\bibitem{KohayakawaMRW01}
Y.~Kohayakawa, F.K. Miyazawa, P.~Raghavan, and Y.~Wakabayashi.
\newblock Multidimensional cube packing.
\newblock In {\em Electronic Notes of Discrete Mathematics}, volume~7. Elsevier
  Science, 2001.
\newblock Presented at the Brazilian Symposium on Graphs and Combinatorics.

\bibitem{LeungTWYC90}
J.~Y-T. Leung, T.~W. Tam, C.~S. Wong, G.~H. Young, and F.~Y.~L. Chin.
\newblock Packing squares into a square.
\newblock {\em Journal of Parallel and Distributed Computing}, 10:271--275,
  1990.

\bibitem{LiC90b}
K.~Li and K-H. Cheng.
\newblock A generalized harmonic algorithm for on-line multidimensional bin
  packing.
\newblock {TR UH-CS-90-2}, University of Houston, January 1990.

\bibitem{MeirM68}
A.~Meir and L.~Moser.
\newblock On packing of squares and cubes.
\newblock {\em J. Combinatorial Theory Ser. A}, 5:116--127, 1968.

\bibitem{MiyazawaW00a}
F.~K. Miyazawa and Y.~Wakabayashi.
\newblock Cube packing.
\newblock In {\em Proc. 4th Latin American Theoretical INformatics.}, volume
  1776 of {\em Lecture Notes in Computer Science}, pages 58--67, Punta del
  Este, Uruguay, 2000. Springer-Verlag.

\bibitem{MiyazawaW0xx}
F.~K. Miyazawa and Y.~Wakabayashi.
\newblock Parametric on-line algorithms for packing rectangles and boxes.
\newblock {\em European Journal on Operational Research}, {t}o appear.

\bibitem{SeidenS02}
S.~S. Seiden and R.~Stee.
\newblock New bounds for multi-dimensional packing.
\newblock In {\em Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete
  Algorithms}, pages 486--495, 2002.

\end{thebibliography}

\end{document}
