Approximation Schemes for Multidimensional Packing
Jos´ R. Correa e
Abstract We consider a classic multidimensional generalization of the bin packing problem, namely, packing d-dimensional rectangles into the minimum number of unit cubes. Our two results are: an asymptotic polynomial time approximation scheme for packing ddimensional cubes into the minimum number of unit cubes and a polynomial time algorithm for packing rectangles into at most OPT bins whose sides have length (1 + ), where OPT denotes the minimum number of unit bins required to pack the rectangles. Both algorithms also achieve the best possible additive constant term. For cubes, this settles the approximability of the problem and represents a significant improvement over the previous best known asymptotic approximation factor of 2 - (2/3)d + . For rectangles, this contrasts with the currently best known approximation factor of 1.691 . . .. 1 Intro duction Bin packing problems have attracted much attention in the literature since the seventies. In the one dimensional case the problem consists of using the minimum number of unit (one dimensional) bins to pack a list of items of size at most one. One dimensional bin packing is known to be NP-hard; moreover, no approximation algorithm with approximation factor better than 3/2 can exist unless P = N P . This leads to the consideration of asymptotic performance guarantees: Fernandez de la Vega and Lueker [5] thus settled the approximability of one dimensional bin packing by giving an asymptotic approximation scheme. In spite of that, in many real world applications the one dimensional framework is too limited and extensions to higher dimensions are needed. Unfortunately, the treatment of higher dimensional versions of bin packing has not been as satisfactory as the one dimensional case so far. Several generalizations of one dimensional bin packing have been considered. Square packing, vector packing and rectangle packing seem to be the most comResearch Center, Massachusetts Institute of Technology, Cambridge, MA 02139-4307. jcorrea@mit.edu  Lab oratoire d'Informatique, Ecole Polytechnique, 91128 Palaiseau Cedex. kenyon@lix.polytechnique.fr
 Op erations



Claire Kenyon



monly known extensions. The square packing problem consists of packing a list of squares into the minimum number of unit squares (bins). Leung et al. [10] proved that deciding whether a list of squares can be packed in a unit square is NP-hard; therefore, square packing is NP-hard. This immediately implies [6] that there is no better than 2 approximation algorithm for square packing unless P = N P . On the other hand, the best known asymptotic approximation algorithms for square packing, independently obtained by Seiden and van Stee [13] and Kohayakawa et al. [9], have an asymptotic performance guarantee of 14/9 + for any > 0. Kohayakawa et al.'s algorithm also works in higher dimensions and has an asymptotic approximation factor arbitrarily close to 2 - (2/3)d ; furthermore, it runs in polynomial time when d is a fixed constant. Here we first study the d-dimensional cube packing problem, d-CP for short. For a list I of d-dimensional cubes, let us denote by OPT(I ) the minimum number of unit cubes in which I can be packed. The first main result in this paper reads as follows. Theorem 1.1. There exists an algorithm A which, given a list I of n d-dimensional cubes and a positive number , produces a packing of I into A(I ) copies of [0, 1]d such that: A(I )  (1 + ) OPT(I ) + 1. The running time of A is polynomial for fixed d and . Note that our approximation scheme is best possible in the sense that the hardness result above implies that there can not be an approximation scheme with constant term strictly less than 1. (Nevertheless, there is not enough evidence to rule out the existence of a polynomial time algorithm producing a packing into no more than OPT(I ) + 1 bins.). Theorem 1.1 was independently proved by Bansal and Sviridenko [1] but with an additive constant of O(1), that depends on 1/ , instead of just 1. The rectangle packing problem (or two dimensional bin packing) consists of packing a list of rectangles into the minimum number of unit squares. Recently, Bansal and Sviridenko [1] showed the following very interesting result: there is no asymptotic polynomial

Copyright © 2004 by the Association for Computing Machinery, Inc. and the Society for industrial and Applied Mathematics. All Rights reserved. Printed in The United States of America. No part of this book may be reproduced, stored, or transmitted in any manner without the written permission of the publisher. For information, write to the Association for Computing Machinery, 1515 Broadway, New York, NY 10036 and the Society for Industrial and Applied Mathematics, 3600 University City Science Center, Philadelphia, PA 19104-2688

186


time approximation scheme for rectangle packing unless P = N P . Their strong result contrasts with the best approximation algorithm has an asymptotic guarantee of 1.691... obtained by Caprara [3]. Nevertheless, the approximation gap is still wide. Here is our second main result. Theorem 1.2. There exists an algorithm A which, given a list I of rectangles and a positive number , produces a packing of I into A(I ) copies of [0, 1 + ]2 such that: A(I )  OPT(I ), where OPT(I ) is the minimum number of unit cubes in which I can be packed. The running time of A is polynomial for fixed . The last theorem is also best possible in the sense that the constant cannot be improved and that there is no APTAS for rectangle packing. In Section 2, we prove Theorem 1.1. Besides using extensions of the approach of Fernandez de la Vega and Lueker [5], the main idea behind the hypercube packing algorithm is to divide the input list into three sets, "large", "medium" and "small", in such a way such that the medium cubes are negligible. As a warm up, we first see how an almost optimal packing of the small cubes can be found, then we do the same for large cubes; finally we bring the pieces together and show how the appropriate partition is found. In Section 3, we prove Theorem 1.2. There is no natural total order on rectangles, hence the rounding technique used by Fernandez de la Vega and Lueker does not seem to extend here. Hence, we round sizes in a straightforward manner, at the cost of enlarging the bin sizes from [0, 1]2 to [0, 1 + ]2 . This enables one to deal with rectangles which are both wide and tall. The main problem is to deal with the rectangles which are either very wide and flat or very thin and tall, and for either kind we can essentially use the strip-packing algorithm of Kenyon and R´mila [7]. Our algorithm thus relies e on an appropriate partition of rectangles into "large", "small", "horizontal", "vertical", and "medium", in such a way that the medium rectangles are negligible. It only remains to mix gracefully the various kinds of rectangles; this requires discretizing a near-optimal solution appropriately so as to be able to "guess" not only where the large rectangles go, but also the areas used to pack horizontal rectangles and the areas used to pack vertical rectangles. Finally, in Section 4, we discuss a related packing problem with applications in VLSI design. Specifically, we show how the ideas in Section 3 can be used to obtain a PTAS for this problem.

2

Hyp ercub e Packings

2.1 Definitions and Preliminaries. We adopt two standard assumptions in multidimensional bin packing: first, items are allowed to "touch" i.e., they can intersect in a face; second, items can not be rotated (orthogonal packing without rotation). A d-dimensional cube is given by a positive number a, representing the length of its side. Since we will pack squares into unit squares, we need to assume a  1. Given an input list I of n d-dimensional cubes with sides of length ai  [0, 1] for i = 1, , . . . , n, the volume n of the list is defined as: v ol(I ) = i=1 ad . Given two i cubes and their positions in the space, we say that they are nonoverlaping if their interiors are disjoint. A packing of I into k bins, is a positioning of the cubes into k copies H1 , . . . , Hk of the unit hypercube [0, 1]d , so that no two cubes overlap. The d-dimensional cube packing problem consists of finding a packing of I into the minimum number of bins, OPT(I ). We denote A(I ) the number of bins algorithm A uses to pack I . We now establish a simple result that will be needed later. Lemma 2.1. Let S be a set of n nonoverlaping d-dimensional cubes positioned inside [0, 1]d . Then, [0, 1]d \ S can be seen as the union of no more than (2n + 1)d nonoverlaping d-dimensional rectangles. Proof. Extending each facet of each cube in S , we obtain a grid in [0, 1]d consisting of (2n + 1)d cells. Observation 2.1. In the last lemma we can assume without loss of generality that in the set S there is a cube touching each of the hyperplanes xi = 0, for i = 1, . . . , d. Thus, [0, 1]d \ S can be seen as the union of no more than (2n)d nonoverlaping d-dimensional rectangles. Observation 2.2. In the 2-dimensional case, no more than 3n rectangles are needed to cover [0, 1]2 \ S . This bound can be seen as fol lows. For each square in S draw an horizontal line at its top and bottom until it intersects some other square as in Figure 1. Assuming the bottom-most square is at height 0, we have drawn 2n - 1 horizontal lines. This partitions the unit square into at most 3n rectangles (two to the side of each square and another to the top of each square in S ) plus the original n squares. 2.2 Packing Small Cub es. In this section we look at multidimensional cube packing in case all cubes are small. In this setting we are given an input list S of cubes with sides ai   for some positive (small) constant  . We will use a multidimensional version of

187


The same argument above applies in general and the total wasted space can be bounded by · j rj +
=1

id

·

=1

j

=i

rj  2

i

d ri .

=1

Figure 1: Decomposing the unit square into rectangles the Next-Fit-Decreasing-Height shelf heuristic (NFDH). Coffman, Garey, Johnson, and Tarjan [2] analyzed this heuristic in the context of strip packing pointing out properties closely related to what we extend here to higher dimensions. In two dimensions, the NFDH algorithm is a level algorithm which uses the next-fit approach to pack the sorted (by nonincreasing size) list of squares. The squares are packed, left-justified on a level (shelf ) until the next rectangle will not fit. This rectangle is used to define a new level and the packing continues on this level. The earlier levels are not revisited. In general we define the NFDH heuristic inductively. Assume we know how to perform NFDH in d - 1 dimensions. The d-dimensional NFDH heuristic will look at a facet F of the bin and pack squares on it using its d - 1 dimensional version. After it finishes packing the facet, it will cut off from the bin a d-dimensional rectangle (slice) with base F and height a1 . It will proceed packing the remaining list in the rest of the bin. Lemma 2.2. Let S denote the instance and assume al l cubes in S have side smal ler than  . Consider the NFDH heuristic applied to cubes in S . If NFDH can not place any other cube in a rectangle R of size r1 × r2 × · · · × rd (with ri  1), the total wasted (unfil led) space in that bin is no more than: 2 id ri

Note that, as in the two-dimensional case, only for i = 1 we waste the volume of two slices. Observation 2.3. If in the previous lemma we are using the NFDH heuristic to place cubes in many rectangles, a slightly more careful argument (which wil l bound the height of slice 1 of a given rectangle Ri with the size of the smal lest item in the last slice of rectangle Ri-1 ) can be used to improve the bound on the wasted space in d rectangle R to:  i=1 ri .

Corollary 2.1. Let S denote the instance and assume al l cubes in S have side smal ler than  , then N F DH (S )  (1 + 2d )v ol(S ) + 1.

That is, NFDH is an APTAS when al l cubes are smal l. 2.3 Packing Large Cub es. We now concentrate in the case of packing large cubes. In this case we are given an input list L of n cubes whose sides are at least  . For simplicity, we split the analysis into two steps (as in [5, 14]). Lemma 2.3. If the input list L contain only large cubes, say ai   for al l i = 1, . . . , n and there are only K different cube sizes for some constant K . Then, we can solve d-CP optimal ly in polynomial time. Proof. Clearly the number of items that fit in a bin is bounded by M = 1/ d . Let us see that the number of bin types R is also constant. Assume cubes of type i have side length equal to i . A bin type will be denoted by a vector (x1 , x2 , . . . , xK ) i.e., x1 cubes of type 1, x2 cubes of type 2, up to xK cubes of type K , that fit in a bin. If a given vector of cubes fit in a bin, they have fit in an arrangement (position) that place their vertices in points with coordinates belonging to the set: . K i iK i i : i  Z + and 0  Z i i  1 C=
=1 =1

=1

Proof. The key idea of the proof is that the smallest cube in slice i is larger than the largest cube in slice i + 1. This says that the volume covered by cubes in slice i is almost as big as (could be even bigger) the total volume of slice i + 1. Let us denote by h1 , h2 , . . . , hl the heighl of the t slices generated by the algorithm. Clearly i=1 hi  1 -  . For d = 2 the total wasted space can be bounded by 2 r1 +  r2 . The factor 2 r1 comes from the first slice (that we cannot bound) and the wasted space above the last slice while the factor  r2 arises from the wasted space to the right of each slice.

Indeed, given a general placement of the cubes in the bin, fix a dimension l = 1, . . . , d and sort the cubes by their leftmost point in their l-th coordinate. Now push the cubes one-by-one, starting from the cubes with smaller l-th coordinate, a little bit to the left until the

188


vertices' l-th coordinates belong to C . By doing this for all coordinates we obtain the claimed result. Now let C denote the cardinality of the set C . Since K i   any point i=1 i i in C will satisfy i  1/ for all i = 1, . . . , K . Hence, C  (1/ )K which is a (huge) constant. This implies that in a bin type all cubes will be placed with their vertices in C d . Then, Cd M K possible bin types, which is there is at most M again a constant. Moreover, we can check in constant time if a given vector (x1 , . . . , xK ) is a bin type or not. Therefore, both M and R are constants and clearly OPT(L)  n. Hence, we can try all possible packs ngs i n in polynomial time, in fact no more than +R uch R packings can exist. Lemma 2.4. If ai   for al l i = 1, . . . , n then there is a (1 +  ) approximation algorithm for d-CP. Proof. Let L denote the given instance list. Sort the n cubes in nonincreasing order of sizes and partition them in K = 1/ d+1 groups, each containing at most Q = n/K cubes. We construct two instances J (resp. J ) by rounding up (resp. down) all items in each group to the largest (resp. smallest) cube in the group. Clearly OPT(J
)

The general asymptotic polynomial time approximation scheme for square packing is as follows: (1) Let I be the input list and > 0 fixed. Consider i the sequence , 3, . . . , 2 -1 , . . . and let Mi = {j : i+1 i aj  [ 2 -1 , 2 -1 )}. (2) Take M := Mi for some index i satisfying v ol(Mi )  OPT(I). Define the set of large items i as L = {j : aj > 2 -1 } and the set of small items i+1 as S = {j : aj  2 -1 }. (3) Find an almost optimal packing of L as in Lemma 2.4. (4) Use NFDH to pack as many squares in S as possible using only the remaining space in the already opened bins (possibly a set S  S was not packed). (5) Use NFDH using only new bins to pack M  S
.

From now on, we call this algorithm as algorithm A. We analyze its running time and prove that satisfies the bound in Theorem 1.1. Analysis of the Running Time. It is clear that steps (3)-(5) take polynomial time for fixed d and . We then only need to see that in step (1)-(2) we can find the set Mi such that v ol(Mi )  OPT(L) in polynomial time. Indeed, since: i ol(Mi )  OPT(I )
 1/ v

 OPT(L)  OPT(J ).

Moreover, the argument of Fernandez de la Vega and Lueker applies here as well, then, OPT(J )    OPT(J ) + Q OPT(L) + Q (1 +  ) OPT(L).

The last inequality follows directly from OPT(L)  n d together with Q  n d+1 . Therefore, the algorithm is to first round the instance and then apply the previous lemma to solve the rounded instance optimally. 2.4 The General Case in Two Dimensions. In this section we prove Theorem 1.1 in the case cubes of any size are allowed to be part of the input list that we now denote by I . Although we already know how to construct almost optimal packings of only big and only small cubes separately, we can not directly apply the algorithms in the previous sections to construct a packing in the general case. One extra step will be required to allow the combination of the previously seen algorithms. For the sake of simplicity in the notation we work in this section only in the two dimensional case. The extension to higher dimensions is straightforward and discussed at the end of the section.

and there are 1/ terms (a constant amount) in the sum. We can find an index i with the desired property by exhaustive search. Hence, algorithm A runs in polynomial time. Analysis of the Algorithm. To prove that algorithm A satisfies the result in Theorem 1.1, we need to distinguish two cases depending on what the set S was after step (4). In both cases the bound in the theorem holds. (i) After step (4), S is empty. In this case, after step (4) the number of bins algorithm A has opened is bounded by (1 + 2
i

-1

) OPT(L  S )  (1 + ) OPT(I ).

And it only remains to pack the squares in M . For that purpose algorithm A needs at most (1 + 2
i

-1

) OPT(I) + 1  2 OPT(I) + 1

189


new bins. It follows that the total number of bins used by A was no more than (1 + 3 ) OPT(I ) + 1. (ii) After step (4), S is nonempty. In this case we derive a volume argument for the bins opened to o pack L. Consider a bin containing a subset L i f squares in L, clearly |L |  1/ (2 -1)2 . From Lemma 2.1 [0, 1]2 \ L can be decomposed into no i more than 3/ (2 -1)2 rectangles, these are filled in step (4) of the algorithm (by NFDH) with squares from the set S . Lemma 2.2 tells us that for each rectangle in the partition we will cover i+1 everything but a volume of at most 2 2 -1 (since each rectangle in the partition has sides length no more than 1). Adding over all rectangles, the i+1 total wasted space can be bounded by 2 2 -1 × i 3/ (2 -1)2  6 . This last bound implies that for each bin containing squares in L, at least a fraction (1 - 6 ) of its volume is filled with squares from L  S. To finish the proof note that A(I ) is exactly the sum of the number of bins used up to step (4) and the number of bins used in step (5). The first quantity was bounded in the last paragraph while the second can be bounded by Lemma 2.2. Thus, A(I )   v ol(L  (S \ S )) + 1-6 (1 + 2 )vol(S  M ) + 1 (1 + 12 )vol(I) + 1 (1 + 12 ) OPT(I ) + 1,

Clearly, the running time of the algorithm is again polynomial in the input size if d and are fixed constant. Finally, the analysis of the algorithm is exactly the same in case (i) and very similar in case (ii). The only difference is that we will need to use the bounds from the all small and all large items in the d-dimensional setting. Therefore, the actual numbers we obtain will depend on d, which is a fixed constant. 3 Packing Rectangles The approach taken above could also be attempted for rectangle packing. Unfortunately we run into trouble when rounding the large rectangles. Instead, our approach here consists in relaxing the constraints by allowing to enlarge the bins slightly. Here is the algorithm used to prove Theorem 1.2. The Algorithm. Input. Denote the input list by I . Assume that the ith rectangle has width ai and heign t bi , with h 0  ai , bi  1. Denote also by Sf(I ) = i=1 ai bi , the total surface of the input. Partitioning the Input. For j  {1, 2, . . . , 2/ }, let Mj denote those rectangles such that ai  ( 2j +1 , 2(j +1)+1 ] or bi  ( 2j +1 , 2(j +1)+1 ]. Let i0 be such that the total surface area of the rectangles of Mi0 is minimum. Let = 2i0 +1 , and define the partition I = Mi0  L  H  V  S , where: · L = {i : ai > · S = {i : ai < · H = {i : ai > · V = {i : ai < and bi > } 2 and bi < and bi < 2} 2} 3.1



proving Theorem 1.1 in the two dimensional case. The Higher Dimensional Analysis. The asymptotic approximation scheme in the d dimensional case is almost the same as the one described above. The only difference lies in the sequence in step (1) and the consequent definition of L, M and S . In d dimensions steps (1) and (2) should be replaced by: (1') Let I be the input list and sequence i = d
2(i+1) -1 d2 -1

2 and bi > }

> 0. Consider the

Rounding the Input. We now round every coordinate greater than up to the nearest multiple of . Denote by I the rounded instance. Let C denote the number of distinct rectangles in L: thus L contains i rectangles of type i, for 1  i  C . Rounding and Partitioning the Output. We define bin types by decomposing (1 + ) × (1 + ) squares as follows: · We consider all possible packings of (large) rectangles of type i, 1  i  C , into a (1 + ) × (1 + ) square, such that the corners of the rectangles have coordinates which are integer multiples of . · For each possible packing into a (1 + ) × (1 + ) square, we consider the area of the bin which is still uncovered as a union of small square cells of side length (where each square is positioned at

for i  0,

and let Mi = {j : aj  [i+1 , i )}. (2') Take M := Mi for some i such that v ol(M )  OPT(I). Define the set of large items as L = {j : aj > i and the set of small items as S = {j : aj  i+1 }.

190


integer multiples of H or V.

), and label each cell either

Together with this labeling of the uncovered area, this packing of large rectangles defines a bin type. Let K be the total number of bin types. j Main Lo op. For each (n1 , . . . , nK ) such that u nj  n, we attempt to construct a packing of I sing nj bins of type j , such that the rectangles from L are packed in the spaces reserved for them in the bin type, the cells labeled H are only used for rectangles from H  S and the cells labeled V are only used for rectangles from V  S . This is done as follows. 1. To decide whether the rectangles from L can be placed, we check that for every rectangle type i, i 1  i  C , the number i of type i rectangles in I s less than or equal to the total space available for them: n . 1 umber of type i rectangles i nj · positioned in type j bins
j K

(c) We place rectangles from H in the configurations thus defined, proceeding in a greedy fashion. (d) We cut back into strips of height and place them back into the bins. Let M denote the set of rectangles which: either did not fit in the fractional packing after (c) or are cut in the process (d). Now, we now set aside M . This defines a packing of the rectangles of H \ M into the parts of the bins labeled H . 3. Similarly, we pack the rectangles of V \ M into the parts of the bins labeled V . 4. We pack the rectangles of S into the × cells which have available space, using the Next Fit Decreasing Height (NFDH) algorithm. 5. We expand each bin by adding a thin vertical 1 × O( ) horizontal strip and a this O( ) × 1 vertical strip and use them to pack the rectangles from Mi0  M  M using an O(1)-approximation algorithm such as NFDH in the horizontal strips and FFDW (Width) in the vertical strips. Output. We output the best packing among all feasible packings of L thus constructed. 3.2 Analysis of the Running Time. The running time is relatively easy to analyze. i0  2/ , thus  4/ = (1). The number C of large rectangle types is at most (1/ )2 = O(1). A bin type can be defined by labeling each × cell by H, V , or i  C , thus the 2 number K of bin types is at most (C + 2)1/( ) = O(1), and so the number of iterations through the main loop is at most nK which is polynomial in n. The number of strip widths is at most 1/ = O(1). The number of configurations is at most 22/( ) = O(1). Multiplying, the number of variables in the linear program is O(1). The number of constraints is at most 2/( ) = O(1). The coefficients Ai,r are bounded by O(1) and Bi are written on at most O(log n) bits, hence the linear program can be solved efficiently. The First Fit Decreasing Height and First Fit Decreasing Width algorithms are polynomial time. Overall, the algorithm thus runs in polynomial time.

of linear constraints, if it exists.  , ()  (i) Bi   r xr Air r () h ( ) , xr (  () r, ) xr 0

2. We use the following algorithm for packing the rectangles from H . (a) For each bin type j , consider the union U of the cells labeled H . Drawing horizontal lines at y -coordinates integer multiples of , we can interpret U as a union of horizontal strips of height and width multiple of . For (j ) each integer multiple of , let h denote i he sum of the heights of the strips of width t n a type j bin. Let h denote the total height of the strips of width in the packing which we are currently constructing, h
=

1

nj h

(j ) .

j K

(b) To pack rectangles from H , we will solve the following fractional strip-packing problem. Consider all configurations (w1 , w2 , . . .) of widths which are multiples of and sum to at most 1 + . Let q be the number of such configurations. Let Air denote the number of occurrences of the width i in configuration r. Let Bi denote the sum of all heights of the rectangles of H whose width equals i . We () define one variable xr for each strip width a nd for each configuration r whose widths sum to at most . We find, in polynomial time, a basic feasible solution to the following system

191


3.3

Analysis of Correctness. Sf(Mi0 )  Sf(I).

and Sf(M
)

Lemma 3.1. Proof. Each rectangle of I belongs to at most two 1 sets Mj , thus j 2/ Sf(Mj )  2Sf(I ). The minimum surface is less than the average surface, which is bounded by Sf(I). Lemma 3.2. Let I denote the rounded input. If I can be packed into OPT unit size bins, then I can be packed into OPT (1 + 2 )×(1+2 ) bins in such a way that any rectangle with ai  is positioned at an x-coordinate which is an integer multiple of , and any rectangle with bi  is positioned at a y -coordinate which is an integer multiple of . Proof. Consider the optimal packing of I . Define a partial order H on rectangles as the transitive closure of the relation: i is in relation with i if rectangle i, when translated horizontally to the right by 2 , intersects r . Note that any chain in H contains at most 1/ i ectangles with ai  . Take a total order  which extends H . We take the rectangles one by one in that order and deal with i as follows: we extend i horizontally to the right so that its width becomes ai , we translate it horizontally to the right to that it is positioned at an integer multiple of ; then, for each i  i in increasing order, if i intersects some rectangle i  i then we translate i to the right by 2 . It is easy to check that this constructs a feasible packing. Since the chains in H contain at most 1/ rectangles of width ai  , each rectangle is translated at most 1/ times, hence in total by at most (2 )/ = 2 . Thus the final packing fits in (1 + 2 ) × 1 bins. We then proceed similarly for rounding the bi s into bi . Lemma 3.3. Consider a packing of I into (1 + 2 ) × (1 + 2 ) bins, satisfying the condition of Lemma 3.2. Consider any cel l C = [m , (m + 1) ]×[p , (p + 1) ] in any bin. Then either H  C =  or V  C = . Proof. Assume, for a contradiction, that i  H  C =  and i  V  C = . Since i has width and starting point integer multiples of , it must be that i spans the whole width of C . Similarly, i must span the whole height of C , But then i and i must intersect, a contradiction. Lemma 3.4. Sf(M ) = O( )Sf(I)

= O( )Sf(I).

Proof. Let us only prove the first equation, the second is analogous. Consider the sets Mc and Md denoting the rectangles the were discarded in steps (c) and (d) respectively. Then Mc  Md = M . We prove that both Sf(Mc ) = O( )Sf(I) and Sf(Md ) = O( )Sf(I). To see the first equality, we recall the strip packing analysis by Kenyon and Remila [7]. Consider a fractional strip packing (i.e. a solution the to linear program () in step (2)(b)) xr for all r and . Clearly such solution has at most (2/ ) nonzero coordinates. Fix and let () () x1 , . . . , xk be the nonzero variables corresponding to that . To constrict an integer strip packing we proceed () as follows: Let xj > 0 be the variable corresponding to the current configuration. This configuration will be () () used between levels lj = (x1 + 2) + · · · + (xj -1 + 2) and lj +1 = lj + xj + 2. For each i such that Aij = 0 we draw Aij columns of width i going from level lj to level lj +1 . After this is done for all and all configurations, we take all columns of width i and start filling them up with the corresponding rectangles of the same width in a greedy manner. It is not difficult to show that all rectangles in fit. Now, we take all rectangles whose top end belongs to the interval (lj - 2, lj ], for any and j , and set them aside (they are put in Mc ). The total surface of the removed rectangles is clearly no more than 2 · ( number of constraints ) · ( max item height ) 2 2=4 . =2· · This proves that a fractional strip packing where strips of width are of height h (the linear program in step (2)(b) ), can be turned into an integer strip packing of almost all rectangles where strips of width are of height no more than h . Therefore, the total surface of rectangles in H that may not fit after step (2)(c) is bounded by 2(2/ ) 2 = 4 . In other words Sf(Mc ) = O( )Sf(I). On the other hand, to see that Sf(Md ) = O( )Sf(I). Notice that the rectangles in H have height smaller than 2 and the cut strips of step (2)(d) are of height , the surface of the rectangles put aside in step (2)(d) is no more than a fraction of the surface of H . Hence, he total surface of M is no more than a fraction O( ) of the total surface of the instance. Lemma 3.5. The rectangles in Mi0  M  M the thin strips added along the bins in step (5).
fi ()

t into

192


Proof. Clearly the whole surface of Mi0  M  M is no more than O( )Sf(I). Moreover, we can partition Mi0  M  M into two sets A and B such that: · A contains only rectangles with ai < Sf(A) = O( ) OPT(I ) (A contains M Mi0 ).
a

2 < 2 and nd part of

· B contains only rectangles with bi < 2 < 2 and Sf(B ) = O( ) OPT(I ) (B contains M and part of Mi0 ). Now, FFDW packs A into the OPT(I ) added strips of size O( ) × 1 while NFDH does the work for the rectangles in B . Lemma 3.6. Consider the two-dimensional NFDH heuristic applied to rectangles in S . When NFDH can not place any other rectangle in a bin of size a × b then the total unused space in that bin is no more than: O( 2)(a + b)

At this step we distinguish four types of × cells: the ones completely filled with a rectangle in L, the ones filled with only rectangles in S , the ones filled only with rectangles in H or V , and the ones partly filled with rectangles in H or V and partly with rectangles in S . By the arguments in Lemmas 3.4 and 3.6 all cells are almost filled Namely a fraction (1 - O( )) of their surface is filled. Overall this implies that a fraction (1 - O( )) of the first OPT(I ) bins is filled, and then the total surface that has been filled in the first OPT(I ) (1 + O( )) × (1 + O( )) squares is at least (1 - O( )) OPT(I )(1 + O( ))2 > OPT(I ). Where the inequality follows by choosing the right constants. 4 Concluding Remarks and Related Problems Our algorithms are also related to the optimization version of the following interesting question posed by Moser [12]: Determine the smal lest number x such that any system of squares with total area 1 may be paral lely packed into a rectangle of area x. Bounds for this problems have been obtained by Kleitman and Krieger [8] and by Novotny [11]. Note that, although we do not obtain bounds for this problem. Our algorithm can easily be adapted to obtain a PTAS for the following very related optimization problem. This problem has many applications in computer science, for example in VLSI design: Given a system of n rectangles with total area 1, determine the smal lest number x such that al l n rectangles may be paral lely packed into a rectangle R of area x. Let us I denote the instance. For each rectangle, let ai  (0, 1] denote its width and bi  (0, 1] its height; the total surface of the instance, denoted by Sf(I ), equals 1. To solve this problem note first that the techniques in the paper can be easily adapted to solve the underlying decision problem: Given n rectangles with sides ai , bi  (0, 1], given a rectangle R of size a × b and given  > 0, determine if all n rectangles can be packed in a rectangle of size [(1 +  )a +  ] × [(1 +  )b +  ] or they cannot be packed in R. Consider a given > 0, and denote by  = min{maxi=1,...,n ai , maxi=1,...,n bi }. We distinguish two cases: (i)  > . In this case, we ensure that the sides of the minimum area rectangle in which all n items can be

Proof. The result is very similar to Lemma 2.2 and to a result in [2]. We are now ready to give the overall analysis of the algorithm. Pro of of Theorem 1.2. Consider an input list I and let I be the rounded input. From Lemma 3.2 we know that there is a packing of I into no more than OPT(I ) bins of size (1 + O( )) × (1 + O( )). Consider then the optimal packing in such bins for I satisfying the conditions of Lemma 3.2. By Lemma 3.3 we know that in such packing all cells as in Lemma 3.3 intersect either an rectangle in L, H or V but not two of them. In other words in an optimal packing of I satisfying the conditions of Lemma 3.2 each cell is labeled either V , H , or i for i = 1, . . . , C (where C was the number of distinct large rectangles); or will have no label at all. Clearly, our algorithm will eventually guess a labeling of the cells such that labeled cell in the optimal packing have the same label. At that point the algorithm will find a feasible packing of all rectangles in L and almost all rectangles in H and V . By Lemmas 3.4 and 3.5 the unpacked rectangles Mi0 , M and M are of small surface and they can be packed in the extra space added in step (5) of the algorithm. It only remains to see that the small rectangles S will be successfully packed by NFDH. We prove that is not possible that in step (4) a new bin is opened if already OPT(I ) (1 + O( )) × (1 + O( )) bins have been used. We do this by a surface argument. Suppose, by contradiction, that such new bin is opened in step (4).

193


packed are at least . It is then enough to solve the decision problem, taking  = 2, for all rectangles R such that: ­ Their lower-left corner is (0, 0) and their upper-right corner is on or below the curve xy = 4Sf(I ) = 4 (since the NFDH shelf packing heuristic can always pack I in a square of area 4Sf(I )). ­ The coordinates of their upper-right corner are at least . ­ Their sides length are integer multiples of 2. The number of such rectangles can be evaluated as:
Sf (I )/ 4

1 Sf(I ) dx · x 4

= = <

S f(I ) 4Sf(I ) ln 4 2 1 4 ln 4 2 1 8 ln 4 .

Which is constant. Therefore by solving the decision problem for a constant number of rectangles, we can choose the one with minimum area. Since in this case a and b are guaranteed to be large, [(1 +  )a +  ]  (1 + 2 )a and [(1 +  )b +  ]  (1 + 2 )b. Therefore the best rectangle is guaranteed to have area within a factor of (1 + O( )) that of the optimal one. (ii)   . In this case either all rectangles are flat or all are narrow. Without loss of generality assume they are all narrow. We will pack all rectangles using the F FDH heuristic for strip packing in a strip of width . A slight adaptation of the following theorem ­ shown in [2] ­ proves that all items can be placed in a rectangle of area roughly equal to Sf(I ). Theorem 4.1. In al l rectangles in have width less than or equal to  , then the height F F DH (I ) achieved by the FFDH heuristic (on a strip of width 1) satisfies: F F DH (I )  (1 +  )Sf(I ) + 1.  In our case the width of the strip is and then F F DH finds a packing in a rectangle of size: ( .  Sf(I )  × 1+ )  1 + The volume of such rectangle is then    (1 + )Sf(I) + = (1 + 2 ). Again the result follows in this case.

An interesting open question is to generalize Theorem 1.2 to higher dimensional rectangle packing. This does not seems to be a trivial task since a higher dimensional version of strip packing will be needed (and the hardness result in [1] implies that there is no APTAS for three-dimensional strip packing). Another open problem is to determine the approximability of finding a packing of a set of rectangles with min(ai , bi ) > 1/3 and max(ai , bi ) > 1/2, that uses the minimum number of unit squares. In this case our rounding techniques do not work. The following example illustrates this fact. Suppose we are given 4n rectangles: 2n of them with height a little larger than 1/2 and width a little smaller than 1/2, and 2n with width a little larger than 1/2 and height a little smaller than 1/2. Can we decide in polynomial time if they all fit in n unit squares? Even more, Can we decide if they fit in, say, 1.1n unit squares? This second question is related to finding hardness of approximation results for rectangle packing. As mentioned before, Bansal and Sviridenko [1] showed that unless P = N P there is no APTAS for the classic two dimensional bin packing problem. Their work partially solves this question and gives good evidence that stronger inapproximability results can be obtained. Acknowledgments. The authors would like to thank David Johnson for many useful comments and suggestions regarding the presentation of the paper and for pointing out some minor errors. References
[1] N. Bansal and M. Sviridenko (2004). New approximability and inapproximability results for 2-dimensional bin packing. These Proceedings. [2] E.G. Coffman, Jr., M. R. Garey, D. S. Johnson, and R. E. Tarjan (1980). Performance bounds for leveloriented two-dimensional packing algorithms. SIAM Journal on Computing 9, 808-826. [3] A. Caprara (2002). Packing 2-Dimensional Bins in Harmony, In Proceeding of the 43rd Annual IEEE Symposium on Foundations of Computer Science (FOCS'02). [4] A. Caprara, A. Lodi, and M. Monaci (2003). Fast Approximation Schemes for the Two-Stage, TwoDimensional Bin Packing Problem. Research Report OR/03/6 DEIS. [5] W. Fernandez de la Vega and G.S. Lueker (1981). Bin packing can be solved within 1 + in polynomial time, Combinatorica 1, 349-355. [6] C.E. Ferreira, F.K. Miyazawa, and Y. Wakabayashi (1999). Packing squares into squares. Pesquisa Operacional 19, 349-355. [7] C. Kenyon and E. Remila (2000). A near optimal solution to a two-dimensional cutting stock problem. Mathematics of Operations Research 25, 645-656.

194


[8] D.J. Kleitman and M. Krieger (1975). An optimal bound for two dimensional packing. In Proceeding of the 16th Annual IEEE Symposium on Foundations of Computer Science (FOCS'75). [9] Y. Kohayakawa, F.K. Miyazawa, P. Raghavan, and Y. Wakabayashi (2001). Multidimensional Cube Packing, In Proceedings of the Brazilian Symposium on Graphs, Algorithms and Combinatorics (GRACO 2001). [10] J. Y-T. Leung, T.W. Tam, C.S. Wong, G.H. Young, and F.Y.L. Chin (1990). Packing squares into a square. Journal of Paral lel and Distributed Computing 10, 271275 [11] P. Novotny (1996). On packing of squares into a rectangle. Archivum Mathematicum 32, 75-83. [12] L. Moser (1965). Poorly formulated unsolved problems is combinatorial geometry. Mimeographed. [13] S.S. Seiden and R. van Stee (2003). New Bounds for Multidimensional Packing, Algorithmica 36, 261-293. [14] V. Vazirani (2001). Approximation Algorithms, Springer-Verlag, Berlin.

195