Multidimensional Cube Packing^{∗}

Y. Kohayakawa^{†}  F.K. Miyazawa^{‡}  P. Raghavan^{§}  Y. Wakabayashi^{†}

September 12, 2002

Abstract

We consider the d-dimensional cube packing problem (d-CPP): given a list L of d-dimen-sional cubes and (an unlimited quantity of) d-dimensional unit-capacity cubes, called bins, find a packing of L into the minimum number of bins. We present two approximation algorithms for 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.

Key Words: Approximation algorithms, multidimensional bin packing, asymptotic performance.

1 Introduction

We consider a generalization of the one-dimensional bin packing problem, called here d-dimensional cube packing problem (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 bins, find an orthogonal packing of L into the minimum number of bins. This problem is in fact a special case of the d-dimensional bin packing problem (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.

∗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).

†Instituto de Matemática e Estatística — Universidade de São Paulo. Rua do Matão, 1010 — 05508–090 — São Paulo–SP — Brazil, {yoshi,yw}@ime.usp.br.

‡Instituto de Computação — Universidade Estadual de Campinas, Caixa Postal 6176 — 13084–971 — Campinas– SP — Brazil, fkm@ic.unicamp.br.

§Verity, Inc., 892 Ross Drive, Sunnyvale, CA 94089, USA, pragh@verity.com.

In 1989, Coppersmith and Raghavan [4] presented an online algorithm for d-BPP with asymptotic performance bound (3 · 2^{d} + 1)/4. This algorithm, when specialized to d-CPP, has asymptotic performance bound (3/2)^{d} − (3/4)^{d} + 1. In [13], Miyazawa and 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 [8] and Fernandez de la Vega and Lueker [6]. For a recent survey on this case, see Coffman, Garey and Johnson [3]. For 2-BPP the algorithm with the best asymptotic performance bound is due to Chung, Garey and Johnson [1], with bound 2.125. For 3-BPP Li and Cheng [11] and Csirik and van Vliet [5] 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 [2].

We present two approximation algorithms for 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 [15] presented an algorithm for d = 2 with bound 14/9 + ϵ that uses an idea similar to the one we present in this paper. It is most likely that the extended abstract [9], where we announced a comparable result, with explicit formulas for general d and full description of our algorithms, was unknown to those authors.

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.

2 Notation and definitions

Given a cube c, the 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 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.

Given a list L of cubes, and an algorithm A, we denote by A(L) the number of bins used by algorithm A when applied to L, and by OPT(L) the number of bins used by an optimal packing of L. If P is a packing of L, we denote the number of bins used in P by |P|. Some of our algorithms partition the input list L into sublists L_{1}, …, L_{k} and then apply specialized algorithms for each sublist L_{i} generating a partial packing P_{i}. We denote the packing obtained by the union of these packings by P_{1} ∪ … ∪ P_{k}. We say that an algorithm A has asymptotic performance bound α if there exists a constant β such that A(L) ≤ α · OPT(L) + β for all input lists L. If β = 0, we also say that α is an absolute performance bound for algorithm A. We note that 2-CPP cannot be approximated within 2 − ϵ in the absolute sense, unless P = NP (see [7], where this result is deduced from [10]). 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.

3 Restricted d-CPP

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

3.1 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 ϵ. We denote the set of such instances by I_{ϵ,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 ∈ I_{ϵ,k,d}, denote by D(L) = (s_{1}, s_{2}, …, s_{k}) the list of different sizes in the list L and by M(L) = (m_{1}, m_{2}, …, 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 P is canonical if no cube in P 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 canonical pattern. With this in mind, we can compute all possible positions ℙ^{d}(L) in a bin where a cube of L can be packed. We set p(L) := {p := b_{1}s_{1} + b_{2}s_{2} + ⋯ + b_{k}s_{k} : 0 ≤ p ≤ 1, 0 ≤ b_{i} ≤ m_{i}}, and define ℙ^{d}(L) as the set p(L)^{d} = p(L) × … × p(L).

Claim 3.1 For a given list L in I_{ϵ,k,d}, the cardinality of ℙ^{d}(L) is bounded by a value that depends only on k, ϵ and d.

Proof. Since each cube of L has size at least ϵ, we have b_{i} ≤ ⌊1/ϵ⌋ for all i. Thus we can conclude that (⌊1/ϵ⌋ + 1)^{k} is an upper bound on p(L). Therefore, we have |ℙ^{d}(L)| ≤ (⌊1/ϵ⌋ + 1)^{kd}.

For L ∈ I_{ϵ,k,d}, let ρ_{ϵ,k,d}(L) denote the number of all possible canonical patterns of L. The following result is immediate.

Claim 3.2 The value ρ_{ϵ,k,d}(L) is bounded by a value that depends only on k, ϵ and d. Proof. Note that the number of canonical patterns for L consisting of exactly i cubes is bounded by

k^{i}\binom{|ℙ^{d}(L)|}{i}.

Therefore,

ρ_{ϵ,k,d}(L) ≤ k\binom{|ℙ^{d}(L)|}{1} + k^{2}\binom{|ℙ^{d}(L)|}{2} + ⋯ + k^{ϵ^{−d}} \binom{|ℙ^{d}(L)|}{ϵ^{−d}},

and the result follows.

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

Lemma 3.3 Let ϵ, k and d be fixed positive numbers and L an instance of d-CPP with L ∈ I_{ϵ,k,d}. Then L can be packed optimally in polynomial time by the algorithm R_{ϵ,k,d}.

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)^{ρ}, where ρ := ρ_{ϵ,k,d}(L).

3.2 Restricted size

In this section, we consider instances where we only have restriction on the minimum size of a cube. We denote by I_{ϵ,d} the set of all instances consisting of cubes with size greater than ϵ.

We shall make use of the linear rounding technique presented by Fernandez de la Vega and Lueker [6] to obtain an asymptotic approximation scheme R_{ϵ,d} for instances in I_{ϵ,d}.

Given two instances X and Y for d-CPP, we write X ⪯ Y if there is an injection f: X → Y such that s(c) ≤ s(f(c)) for all c ∈ 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 ⪯ \overline{X}. The following claim is immediate.

Claim 3.4 If X and Y are two instances for d-CPP with X ⪯ Y, then OPT(X) ≤ OPT(Y).

We are now ready to describe the algorithm R_{ϵ,d}. Algorithm R_{ϵ,d}(L) Input: L ∈ I_{ϵ,d}

1. If L contains < 2/ϵ^{d+1} cubes, find an optimal packing exhaustively and return this packing. Otherwise, let L = (c_{1}, …, c_{n}) be the input list sorted in non-increasing order of size.

2. Set q := ⌊nϵ^{d+1}⌋ and partition L into groups G_{0}, G_{1}, …, G_{k} such that

G_{0} ⪰ G_{1} ⪰ ⋯ ⪰ G_{k},
where |G_{i}| = q for all i = 0, …, k − 1,
and |G_{k}| ≤ q.

3. Let P_{0} be the packing obtained by placing each cube of G_{0} into a different bin

4. Let J := ⋃_{i=1}^{k} G_{i} and Ĵ:= ⋃_{i=1}^{k} \overline{G}_{i}.

5. Let P̂ be the packing of Ĵ generated by the algorithm R_{ϵ,k,d}; and let P_{1} be the packing of J corresponding to Ĵ.

6. Return P_{0} ∪ P_{1}.

Lemma 3.5 For all input list L ∈ I_{ϵ,d}, we have

R_{ϵ,d}(L) ≤ (1 + ϵ) OPT(L).

Furthermore, R_{ϵ,d} is a polynomial time algorithm.

Proof. It suffices to consider the case in which n ≥ 2/ϵ^{d+1}. In step 2 we partition the sorted list L into k + 1 groups G_{i} each of which consists of q = ⌊nϵ^{d+1}⌋ cubes, except perhaps for the last group, which may have fewer cubes. Note that k + 1 = ⌈n/⌊ϵ^{d+1}n⌋⌉ ≤ ⌈2/ϵ^{d+1}⌉ and, therefore, the number of different cube types in list Ĵ is bounded by a value that depends only on ϵ and d. Since \overline{G}_{i} ⪯ G_{i−1} (i = 1, …, k) we have Ĵ ⪯ L. From Lemma 3.3 and Claim 3.4, we have

|P_{1}| = |P̂| = OPT(Ĵ) ≤ OPT(L).  (1)

The packing of G_{0} uses at most q bins, therefore

|P_{0}| ≤ q = ⌊nϵ^{d+1}⌋ ≤ nϵ^{d+1} ≤ ϵ V (L) ≤ ϵ OPT(L).  (2)

From inequalities (1) and (2), we have

R_{ϵ,d}(L) = |P_{0}| + |P_{1}| ≤ OPT(L) + ϵ OPT(L) ≤ (1 + ϵ) OPT(L),

as required.

We now turn to an algorithm that will be used only in the improved version of our algorithm (see Section 4.2). This algorithm, which we call R′_{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 R′_{1/3,d} is a generalization for d-CPP of an algorithm presented by Ferreira, Miyazawa and Wakabayashi [7] for 2-CPP.

Algorithm R′_{1/3,d}(L)
Input: L ∈ I_{1/3,d}

1. Partition the list L into the two sublists

L′ := {c ∈ L : s(c) > 1/2}  and  L′′ := L \ L′.

2. Sort the cubes in L′ in non-decreasing order of their sizes. Let L′ = (c′_{1}, …, c′_{n′}).

3. Sort the cubes in L′′ in non-increasing order of their sizes. Let L′′ = (c′′_{1}, …, c′′_{n′′}).

We have

\frac{1}{3} < ⋯ ≤ s(c′′_{1}) ≤ \frac{1}{2} < s(c′_{1}) ≤ ⋯

4. Call the subroutine SR_{1/3,d} with parameters (L′, L′′).

Subroutine SR_{1/3,d}(L′, L′′)

(a) If L′ = ∅ and L′′ = ∅ then return ∅;

(b) else if L′ = ∅ then generate a packing P placing the first m := min{2^{d}, n′′} cubes of L′′ into one bin;

(c) else if L′′ = ∅ then generate a packing P placing the cube c′_{1} into one bin;

(d) else if s(c′_{1}) + s(c′′_{1}) > 1 then generate a packing P placing m := min{2^{d}, n′′} cubes of L′′ into one bin;

(e) else generate a packing P placing the cube c′_{1} and m := min{2^{d} −1, n′′} cubes of L′′ into one bin.

(f) Remove from L′ and L′′ the cubes that have been packed.

(g) Return P ∪ SR_{1/3,d}(L′, L′′).

First we prove that the packing generated by the algorithm R′_{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.

Lemma 3.6 Let L ∈ I_{1/3,d} be an instance for d-CPP, L′ := \{c ∈ L : s(c) > \frac{1}{2} \} and L′′ := L \ L′. Then the algorithm R′_{1/3,d} applied to L generates a packing where each bin, except for possibly one, has one of the following configurations.

C1 : configuration consisting of 1 cube of L′ and 2^{d} − 1 cubes of L′′. C2 : configuration consisting of exactly 1 cube of L′. C3 : configuration consisting of 2^{d} cubes of L′′.

Proof. Note that each call of the subroutine SR_{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′′ = ∅ and therefore the next bins to be generated, if any, will have configuration C2.

Theorem 3.7 The algorithm R′_{1/3,d} finds an optimal solution for d-CPP restricted to instances L ∈ I_{1/3,d} in polynomial time.

Proof. The algorithm R′_{1/3,d} partitions the list L into two sublists L′ and L′′, sorts them and calls the subroutine SR_{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 SR_{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 P^{∗} of L′ ∪ 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 P^{∗} does not have c′′_{1} with any other cube in L′. Let B^{∗} be the bin of P^{∗} 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 ∈ B \ B^{∗} and C^{∗} is the bin of P^{∗} containing c, then we can clearly exchange any cube in B^{∗} \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.

4 Approximation algorithms for d-CPP

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 NFDH generates t-dimensional strips (using dimensions 1, …, t) using (t − 1)- dimensional strips (dimensions 1, …, 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 [12].

The following result was proved by Meir and Moser [12] for the algorithm NFDH. We can derive from it two corollaries which will be useful to prove the bounds for our algorithms.

Theorem 4.1 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} × a_{2} × ⋯ × a_{d} parallelepiped if

V (L) ≤ s^{d} + (a_{1} − s)(a_{2} − s) ⋯ (a_{d} − s).

Corollary 4.2 Let P be the packing into unit bins obtained by applying the algorithm NFDH to a list L consisting of d-dimensional cubes with maximum size ϵ. Then each sublist of cubes packed in a bin used by P, except for possibly one, has volume greater than (1 − ϵ)^{d}. Proof. Suppose P uses m bins, and let L_{i} = (c_{1}^{i}, …, c_{n_{i}}^{i}) be the sublist packed in the i-th bin. Since the set L_{i} ∪ {c_{1}^{i+1}}, for 1 ≤ i ≤ m − 1, could not be packed by the algorithm NFDH in the i-th bin, we have V (L_{i} ∪ {c_{1}^{i+1}}) > ϵ^{d} + (1 − ϵ)^{d}. Therefore,

V (L_{i}) > ϵ^{d} + (1 − ϵ)^{d} − V (c_{1}^{i+1}) ≥ (1 − ϵ)^{d}

for i = 1, …, m − 1. Corollary 4.3 Let P 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 P, except for possibly one, has volume at least (1/2)^{d}. 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 4.2 to this list the result is immediate.

We now state a technical lemma [14] that will be useful in the proofs of Theorems 4.5 and 4.7. Lemma 4.4 Suppose a, b, γ, δ are real numbers such that a > 0 and 0 < γ < δ < 1. Then

\frac{a + b}{max\{a, γa + δb\}} ≤ 1 + \frac{1 − γ}{δ} .

4.1 First Algorithm

Now we are ready to describe the first algorithm of this section, called A′_{ϵ,d}, which depends on a parameter ϵ. This parameter is used to subdivide the list L into two sublists: one consisting of “large” cubes (size greater than ϵ) and the other consisting of “small” cubes. For the large cubes we use the asymptotic approximation scheme presented in Section 3.2, 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.

Algorithm A′_{ϵ,d}(L)

1. Partition the list L into the two sublists

L′ := {c ∈ L : s(c) > ϵ}  and  L′′ := L \ L′.

2. Generate a packing P′_{1} of L′ using the algorithm R_{ϵ,d}.

3. Generate a packing P′_{2} of L′ using the algorithm NFDH.

4. Let P′ be a packing in {P′_{1}, P′_{2}} that uses the least number of bins.

5. Generate a packing P′′ of L′′ using algorithm NFDH.

6. Return P′ ∪ P′′.

Theorem 4.5 For fixed values of d and ϵ the algorithm A′_{ϵ,d} runs in polynomial time. Furthermore, we have

A′_{ϵ,d}(L) ≤ α_{ϵ,d}OPT(L) + 2,

where α_{ϵ,d} → 2 − (1/2)^{d} as ϵ → 0.

Proof. Since the algorithms R_{ϵ,d} and NFDH are polynomial time algorithms, A′_{ϵ,d} is also a polynomial time algorithm. Let us analyse the performance of A′_{ϵ,d}.

Let n′ := |P′| − 1 and n′′ := |P′′| − 1. ¿From steps 3 and 4 and Corollary 4.3, we have

V (L′) ≥ \frac{1}{2^{d}} (|P′_{2}| − 1) ≥ \frac{1}{2^{d}} (|P′| − 1) ≥ \frac{1}{2^{d}} n′.  (3)

¿From step 5 and Corollary 4.2, we have

V (L′′) ≥ (1 − ϵ)^{d}(|P′′| − 1) ≥ (1 − ϵ)^{d}n′′.  (4)

¿From inequalities (3) and (4) and the fact that the volume of the cubes in L is a lower bound for the optimum packing, we conclude that

OPT(L) ≥ V (L) = V (L′) + V (L′′) ≥ \frac{1}{2^{d}} n′ + (1 − ϵ)^{d}n′′.  (5)

The packing P′_{1} of sublist L′ is generated by an asymptotic approximation scheme (see Lemma 3.5). Since from step 4 the packing P′ of L′ is such that |P′| ≤ |P′_{1}|, we have

OPT(L) ≥ OPT(L′) ≥ \frac{1}{1 + ϵ} |P′| ≥ \frac{n′}{1 + ϵ}.  (6)

¿From inequalities (5) and (6), we have

OPT(L) ≥ max \{\frac{n′}{1 + ϵ}, \frac{1}{2^{d}} n′ + (1 − ϵ)^{d}n′′\} .  (7)

Since A′_{ϵ,d}(L) = |P′| + |P′′|, we obtain

A′_{ϵ,d}(L) = (n′ + 1) + (n′′ + 1)
= \frac{n′ + n′′}{OPT(L)}OPT(L) + 2
≤ α_{ϵ,d}OPT(L) + 2,

where α_{ϵ,d} = (n′ + n′′)/(max{n′/(1 + ϵ), (1/2^{d})n′ + (1 − ϵ)^{d}n′′}) (see (7)). From Lemma 4.4, we conclude that lim_{ϵ→0} α_{ϵ,d} ≤ 2 − (1/2)^{d}.

Proposition 4.6 The asymptotic performance bound 2 − (1/2)^{d} of the algorithm A′_{ϵ,d} is tight.

Proof. Let L′ be a list of n′ cubes of size 1/2 + ξ, where n′ is a large integer and ξ is a small real such that ξ < ϵ and 1/ξ is an integer. Let L′′ be a list of n′′ := ⌈(1 − 1/2^{d})n′⌉/ξ^{d} cubes of size ξ.

Consider a packing P of a list L := L′ ∪ L′′ generated by the algorithm A′_{ϵ,d}. The algorithm A′_{ϵ,d} packs L′ and L′′ separately. For L′ the algorithm uses at least n′ bins. For L′′, the algorithm generates a packing using ⌈(1 − (1/2)^{d})n′⌉ bins. That is, A′_{ϵ,d}(L) = n′ + ⌈(1 − (1/2)^{d})n′⌉.

On the other hand, an optimal packing of L can be found using n′ + 1 bins. Therefore, the ratio A′_{ϵ,d}(L)/OPT(L) can be made as close to 2 − (1/2)^{d} as desired.

4.2 Improved Algorithm

In this section we present an algorithm that is an improvement of A′_{ϵ,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 A_{ϵ,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 ϵ), 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 ϵ), consists of a packing with a good bound for the volume occupation.

The algorithm A_{ϵ,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. Either we have packed all the small cubes into bins of part (i), 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 P′ for the sublist L′. In step 3 we separate the bins of P′ 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.

Algorithm A_{ϵ,d}(L)

1. Partition the list L into the two sublists

L′ := {c ∈ L : s(c) > ϵ}  and  L′′ := L \ L′.

2. Generate a packing P′ of the sublist L′ using algorithm R_{ϵ,d}.

3. Let P′_{1} consist of all bins of packing P′ with volume occupation less than (2/3)^{d}, and let P′_{2} consist of the remaining bins of P′. Let L′_{1} be the cubes in P′_{1}.

4. Generate a new packing P̂′_{1} of L′_{1} as follows

4.1 Let S_{i} := \{c ∈ L′_{1} : s(c) ∈ (\frac{1}{i+1}, \frac{1}{i}]\}, for i = 1, …, 8 and

let S_{9} := \{c ∈ L′_{1} : s(c) ≤ \frac{1}{9}\}. 4.2 Generate a packing P_{12} of S_{1} ∪ S_{2} using the algorithm R′_{1/3,d}, and let U be the

set of bins in P_{12} with configuration C2.

4.3 For i = 3, …, 8, repeat the following steps 4.3.1 If U is empty, pack (up to) i^{d} cubes of S_{i} in a new bin B. 4.3.2 If U is not empty then

Let B be a bin in U; If i ∈ {3, 4, 5} then let m := i^{d} − (i − 1)^{d} else let m := i^{d} − (i − 2)^{d}; Pack (up to) m cubes of S_{i} (around the unique cube in B); Update S_{i}; Remove B from U.

4.4 Pack the cubes in S_{9}, as follows

4.4.1 Subdivide the empty space of each bin B ∈ U (around the unique cube in B) into 3^{d} − 2^{d} smaller bins with size 1/3. Let U′ be the set of these smaller bins.

4.4.2 Pack the cubes of S_{9} into bins of U′ using the algorithm NFDH. Remove

the used bins of U′. Use new unit bins if necessary.

5. Pack the cubes of L′′ into bins U′ using the algorithm NFDH. Use new unit bins if necessary.

6. Return the generated packing P.

Theorem 4.7 For fixed values of d and ϵ the algorithm A_{ϵ,d} runs in polynomial time. Furthermore, we have

A_{ϵ,d}(L) ≤ α_{ϵ,d}OPT(L) + 9,

where α_{ϵ,d} → 2 − (2/3)^{d} as ϵ → 0.

Proof. From steps 2 and 3 and Lemma 3.5, we have

|P′_{1}| + |P′_{2}| = |P′| ≤ (1 + ϵ)OPT(L),  (8)

where P′_{1} consists of the bins of P′ with volume occupation less than (2/3)^{d}.

In step 4, the packing P′_{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}.

In step 4.2 the algorithm R′_{1/3,d} generates an optimal packing P_{12} of S_{1} ∪ S_{2} which contains bins with configurations C1, C2 or C3, described in Lemma 3.6.

The bins of P_{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 P_{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 P_{12} with volume occupation less than (2/3)^{d} are the bins with configuration C2. These are exactly the bins U 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, …, 8. First, let us consider the packing of the cubes in S_{3}. Suppose that U 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 ∈ U after receiving the cubes of S_{3} will have volume occupation

V_{oc}(B) ≥ \frac{1}{2^{d}} + (3^{d} − 2^{d})\frac{1}{4^{d}} ≥ (\frac{2}{3})^{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 U 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) ≥ 3^{d} \frac{1}{4^{d}} ≥ (\frac{2}{3})^{d} ,

except perhaps for the last one.

The analysis for the packing of the sublists S_{4}, …, S_{8} is analogous. We can prove a volume occupation of (2/3)^{d} for each rearranged bin of U, 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 U. Suppose there is a bin B in U. 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 U′, 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 4.2, the algorithm NFDH generates packings into bins B′ ∈ U′ with volume occupation at least (1/3 − 1/9)^{d}. Since we have 3^{d} − 2^{d} bins of U′ inside each bin B of U, the bins B after being filled with cubes of S_{9} will have a volume occupation

V_{oc}(B) ≥ \frac{1}{2^{d}} + (3^{d} − 2^{d}) (\frac{1}{3} − \frac{1}{9})^{d} ≥ \frac{1}{2^{d}} + \frac{2^{d}}{3^{d}} − \frac{4^{d}}{9^{d}} > (\frac{2}{3})^{d} .

If during the packing of cubes in S_{9} the set U′ becomes empty, then the algorithm packs the remaining cubes of S_{9} into new unit bins. From Corollary 4.2, each bin B of this type has volume occupation

V_{oc}(B) > (1 − \frac{1}{9})^{d} > (\frac{2}{3})^{d} .

From the previous inequalities, we can conclude that, after step 4, the only bins in U 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, …, 9).

At this point, we can conclude the following: If all cubes of S_{3}, …, S_{9} were packed inside bins of U, then the packing P̂′_{1} does not use more bins than the optimal packing P_{12}, and therefore the packing P̂′_{1} is also optimal. That is

|P̂′_{1}| ≤ |P′_{1}|.  (9)

If the set U 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 P′_{1} have volume occupation less than (2/3)^{d}, we can conclude that the packing P̂′_{1} has at most 8 bins more than the packing P′_{1}. That is,

|P̂′_{1}| ≤ |P′_{1}| + 8.  (10)

From inequalities (9), (10) and (8), we have

|P̂′_{1}| + |P′_{2}| ≤ (1 + ϵ)OPT(L) + 8.  (11)

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 U′, which are inside the bins of P̂′_{1} with configuration C2. If necessary, new unit bins are used. The analysis of this step is divided into two cases:

Case 1. All cubes of L′′ have been placed inside the bins of U′. In this case, we have not used any new unit bin and, therefore,

|P| = |P̂′_{1}| + |P′_{2}| ≤ (1 + ϵ)OPT(L) + 8.  (12)

Case 2. New unit bins have been used in the packing of L′′. In this case, each bin B of U has been “filled” with cubes in L′′. From Corollary 4.2, the bin B has volume occupation

V_{oc}(B) > (1 − ϵ)^{d} > (\frac{2}{3})^{d} .

Let ˆ P̂′_{1} be the packing P̂′_{1} with the bins of configuration C2 filled with cubes of L′′, and P̂′′ be the packing of the remaining cubes in L′′ into new unit bins. Denote the set of cubes packed in P̂′′ as L̂′′. Since the packing ˆ P̂′_{1} and the packing P̂′_{1} have the same number of bins and the packing P′_{1} is an asymptotically optimal packing, the packing ˆ P̂′_{1} is also an asymptotically optimal packing. Now, the final packing P consists of two parts: an almost asymptotically optimal packing ˆP̂′_{1} ∪ P′_{2},

|ˆP̂′_{1} ∪ P′_{2}| ≤ (1 + ϵ)OPT(L) + 8,

with volume occupation of (2/3)^{d} in each bin, except perhaps in 9 bins; and the packing P̂′′ containing the remaining cubes of L′′ into unit bins. From Corollary 4.2, we have

|P̂′′| ≤ \frac{1}{(1 − ϵ)^{d}} V (L̂′′) + 1.

Proceeding as in the proof of Theorem 4.5, we may conclude that

A_{ϵ,d}(L) ≤ α_{ϵ,d}OPT(L) + 9,

where α_{ϵ,d} = (n′ + n′′)/max{1/(1 + ϵ)n′, (2/3)^{d}n′ + (1 − ϵ)^{d}n′′}. From Lemma 4.4, we have lim_{ϵ→0} α_{ϵ,d} ≤ 2 − (2/3)^{d}.

Finally, note that all steps of the algorithm A_{ϵ,d} can be implemented to run in polynomial time.

Proposition 4.8 The asymptotic performance bound 2 − (2/3)^{d} of algorithm A_{ϵ,d} is tight.

Proof. The proof of this result is similar to the proof of Proposition 4.6. Consider a list L := L′∪L′′, such that L′ has n′ cubes of size 2/3 + ξ and L′′ has n′′ := ⌈(1 − (2/3)^{d})n′⌉/ξ^{d} cubes of size ξ, where n′ is a large integer and ξ is a small real; we omit the details.

5 Open problems

We believe the following problems should be tackled.

Problem 5.1 Is there an asymptotic approximation scheme for d-CPP?

Problem 5.2 Prove better bounds of inapproximability in the absolute sense for the d-dimensional case.

References

[1] F. R. K. Chung, M. R. Garey, and D. S. Johnson. On packing two-dimensional bins. SIAM Journal on Algebraic and Discrete Methods, 3:66–76, 1982.

[2] E. G. Coffman, Jr., M. R. Garey, and D. S. Johnson. Approximation algorithms for bin packing - an updated survey. In G. Ausiello, M. Lucertini, and P. Serafini, editors, Algorithms design for computer system design, pages 49–106. Spring-Verlag, New York, 1984.

[3] E. G. Coffman, Jr., M. R. Garey, and D. S. Johnson. Approximation algorithms (ed. D. Hochbaum), chapter Approximation algorithms for bin packing - a survey. PWS, 1997.

[4] D. Coppersmith and P. Raghavan. Multidimensional on-line bin packing: algorithms and worst-case analysis. Operations Research Letters, 8(1):17–20, 1989.

[5] J. Csirik and A. van Vliet. An on-line algorithm for multidimensional bin packing. Operations Research Letters, 13:149–158, 1993.

[6] W. Fernandez de la Vega and G. S. Lueker. Bin packing can be solved within 1 + ϵ in linear time. Combinatorica, 1(4):349–355, 1981.

[7] C. E. Ferreira, F. K. Miyazawa, and Y. Wakabayashi. Packing of squares into squares. Pesquisa Operacional, 19(2):223–237, 1999.

[8] N. Karmarkar and R. M. Karp. An efficient approximation scheme for the one dimensional bin packing problem. In Proc. 23rd Ann. Symp. on Foundations of Computer Science, pages 312–320, Los Angeles, 1982. IEEE Computer Society.

[9] Y. Kohayakawa, F.K. Miyazawa, P. Raghavan, and Y. Wakabayashi. Multidimensional cube packing. In Electronic Notes of Discrete Mathematics, volume 7. Elsevier Science, 2001. Presented at the Brazilian Symposium on Graphs and Combinatorics.

[10] J. Y-T. Leung, T. W. Tam, C. S. Wong, G. H. Young, and F. Y. L. Chin. Packing squares into a square. Journal of Parallel and Distributed Computing, 10:271–275, 1990.

[11] K. Li and K-H. Cheng. A generalized harmonic algorithm for on-line multidimensional bin packing. TR UH-CS-90-2, University of Houston, January 1990.

[12] A. Meir and L. Moser. On packing of squares and cubes. J. Combinatorial Theory Ser. A, 5:116–127, 1968.

[13] F. K. Miyazawa and Y. Wakabayashi. Cube packing. In Proc. 4th Latin American Theoretical INformatics., volume 1776 of Lecture Notes in Computer Science, pages 58–67, Punta del Este, Uruguay, 2000. Springer-Verlag.

[14] F. K. Miyazawa and Y. Wakabayashi. Parametric on-line algorithms for packing rectangles and boxes. European Journal on Operational Research, to appear.

[15] S. S. Seiden and R. Stee. New bounds for multi-dimensional packing. In Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 486–495, 2002.