New Approximability and Inapproximability results for 2-dimensional bin packing
Nikhil Bansal
Abstract
We study the 2-dimensional generalization of the classical Bin Packing problem: Given a collection of rectangles of specified size (width, height), the goal is to pack these into minimum number of square bins of unit size. A long history of results exists for this problem and its special cases [3, 14, 10, 18, 9, 1, 15]. Currently, the best known approximation algorithm achieves a guarantee of 1.69 in the asymptotic case (i.e. when the optimum uses a large number of bins) [1]. However, an important open question has been whether 2-dimensional bin packing is essentially similar to the 1-dimensional case in that it admits an asymptotic polynomial time approximation scheme (APTAS) [8, 13] or not? We answer the question in the negative and show that the problem is APX hard in the asymptotic case. On the other hand, we give an asymptotic PTAS for the special case when all the rectangles to be packed are squares (or more generally hypercubes). This improves upon the previous best known guarantee of 1.454 for d = 2 [9] and 2 - (2/3)d for d > 2 [15], and settles the approximability for this special case.

Maxim Sviridenko
wp > 0 and height 1  hp > 0. Clearly the N P Hardness of 2-dimensional bin-packing follows for that of 1-dimensional bin packing (which is the special case, when all the heights are exactly 1). The standard measure used to analyze the performance of a packing  algorithm A is the asymptotic approximation ratio RA defined by
n RA = max{A(L)/OP T (L)|OP T (L) = n}  n RA = lim sup RA n

1 Intro duction In the 2-Dimensional Bin Packing Problem rectangles of specified size (width, height) have to be packed into larger squares (bins). The most interesting and wellstudied version of this problem is the so called orthogonal packing without rotation where each rectangle must be packed parallel to the edges of a bin. The goal is to find a feasible packing, i.e. a packing where rectangles do not overlap, using smallest number of bins. Bin packing and its d-dimensional variants have been extensively studied since the 60's both in the context of offline approximation algorithms and online algorithms. A detailed survey can be found in [4, 7]. Throughout this paper we only consider offline algorithms, and give only the relevant results. We assume that every rectangle p has width 1 
of Computer Science, Carnegie Mellon University, Pittsburgh, PA 15213, USA. Email: nikhil@cs.cmu.edu.  IBM T.J. Watson Research Center, Yorktown Heights, 10598, Email: sviri@us.ibm.com.
 Department

where L ranges over the set of all problem instances and A(L) (resp. OP T (L)) denote the number of bins used by A (resp. the optimum algorithm). For 1-dimensional bin packing, De La Vega and Lueker gave the first asymptotic approximation scheme [8]. Later, this was improved by Karmarkar and Karp to give an algorithm which uses Opt + O(log2 Opt) bins [13]. For the 2-dimensional case, the first results were obtained by [3] who gave a 2.125 approximation algorithm. For a long time this was the best known, until a 2 + (for any > 0) approximation was obtained (implicitly) by Kenyon and Remila [14]. The recent breakthrough is an elegant 1.691 approximation algorithm due to Caprara [1]. Interestingly, many more results are known for some special cases in which there is a restriction on how the rectangles can be packed in a bin. Two particular cases that are widely studied are Strip Packing and Shelf Packing (details about these can be found in [1] and the references there in). While clever asymptotic approximations schemes are known for some of these special cases, it was unclear whether the general 2-dimensional bin packing problem admits an approximation scheme. For the special case of packing squares in square bins (which is also NPhard by [16]) only algorithms with constant factor approximation ratios were known prior to our work. The first guarantee better than 2.125 was obtained by [10] who gave a 1.988-approximation algorithm. This was later improved to 14/9 + = 1.55 + by Seiden and Stee [18]. Recently, Caprara gave an algorithm and showed that it has approximation in the interval [1.490, 1.507], provided a conjecture is true [1]. The best

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

196


known guarantee prior to our work is due to Epstein and Stee [9] who give an 16/11 + = 1.454 + algorithm for the 2-dimensional case. Finally, for the general d-dimensional hypercube packing case, [15] obtained the first algorithm with approximation ratio 2 - (2/3)d , for fixed d. A related problem is that of Vector Bin packing described as follows: Given a set of n rational vectors p1 , . . . , pn from [0, 1]d , find a partition of the ¯ set into sets A1 , . . . , Am such that ||Ai ||  1 for j ¯ 1  i  m, where Ai = pj is the sum of the Ai vectors in Ai . The ob jective is to minimize m, the size of the partition. For d = 1, the vector bin packing problem is identical to the classical 1-dimensional bin packing, but this is not true for d > 1. Chekuri and Khanna [2] showed a relatively simple connection between d dimensional vector bin packing (for arbitrary d) and graph coloring, which implies that vector bin packing is hard to approximate within O(d1- ) for any > 0. Woeginger [20] showed that the problem is APX hard even for the case of d = 2. The best known result for this problem is an (1 + d + O(ln -1 ))-approximation for any fixed > 0 [2]. This in particular implies an O(ln(d)) approximation for constant d. Another closely related problem is the packing problem where we are given a set of rectangles with non-negative profits. The goal is to maximize the total weight of rectangles which could be packed into a bigger rectangle (or square by scaling). The most recent paper on this problem is due to Jansen and Zhang [11]. They describe few constant factor approximation algorithms for this problem and provide references on the state of the art for it. 1.1 Our Results We show the following results: 1. The 2-dimensional bin packing problem does not admit an asymptotic approximation scheme. This trivially implies the non-existence of an asymptotic PTAS for all d  2. 2. We give the first asymptotic approximation scheme for packing squares into square bins. More generally, we give an APTAS for packing d-dimensional hypercubes into bins for any fixed d. Independently of our result, Correa and Kenyon [6] obtained the same result which is published in this proceedings. They also designed a resource augmented PTAS for the general 2-dimensional rectangle packing problem, i.e. the algorithm which packs rectangles into the optimal number of bins of size (1 + ) × (1 + ). 1.2 Techniques Our result for the APX hardness of 2-dimensional bin packing has ideas similar to those used by Woeginger [20] to show the APX hardness of 2 dimensional vector packing. However, our construction is much more involved than in [20] as there is much less structure on how the rectangles can be packed in

a bin. For example, given a collection of rectangles (or equivalently vectors) p1 , . . . , pn , it is NP-Hard to decide whether these rectangles can be packed in a single bin in the sense of rectangular bin packing (this follows by a simple reduction from the 3-Partition problem). On the other hand, this problem is trivial for vector bin packing. For d > 1 dimensional square (or hypercube) packing, most previous approaches which obtain a constant factor approximation [10, 18, 15, 9] use the classical techniques used for 1-dimensional bin packing. That is, classify the ob jects into large and small. Find a packing of the large ob jects using rounding and exhaustive search, and then pack the remaining small ob jects. In the case when d > 1, the above approach does not directly yield an approximation scheme for the following reason: The gaps left in the bin after packing the large ob jects can have arbitrary structure, and it is not clear how to pack the small ob jects in these gaps without wasting a constant fraction of the space. Our approach is based on a technique due to Sevastianov and Woeginger [19]. We partition the ob jects into 3 sets: large, medium and small. This gives us a sufficient gap between the sizes of the large ob jects and the small ob jects. We pack the medium ob jects separately, and then show how to pack the large and the small ob jects together. MAX SNP Hardness of 2 dimensional bin packing We give a reduction from the Maximum Bounded 3-Dimensional matching problem. Input: Three sets X = {x1 , . . . , xq }, Y = {y1 , . . . , yq } and Z = {z1 , . . . , zq }. A subset T  X × Y × Z such that any element in X, Y , Z occurs in one, two or three triples in T . Note that this implies that q  |T |  3q . Goal: Find a maximum cardinality subset T of T such that no two triples in T agree in any coordinate. Measure: Cardinality of T . Kann [12] was first who proved MAX SNP hardness of the MAX-3-DM. Petrank [17] (Theorem 4.4) proved a refined hardness result, he proved that it is NP-hard to distinguish between instances where |T | = q and instances where |T |  (1 - )q for some constant  > 0. We start with an instance I of MAX-3-DM and we will construct an instance of 2-dimensional bin packing with 5q + 3|T | rectangles. We first define the following integers. Let r = 32q . xi = ir3 + i2 r + 1, y = j r + j r + 2, zi = k r9 + k 2 r7 + 4,
i 6 24

2

for for for

1  i  q, 1  j  q, 1  k  q.

For every triple tl = (xi , yj , zk ) in T , we define an

197


integer tl = r10 - xi - yj - zk + 15 = r10 - k r9 - k 2 r7 - j r6 - j 2 r4 - ir3 - i2 r + 8. Let  = 1/500 and let c = (r10 + 15)/ . Observe that 0 < xi , yj , zk <  c/10 and tl <  c holds for all i, j, k , l. We now describe the rectangles in our instance. A rectangle of width w and height h will be denoted by (w, h). For each element in xi  X we define two rectangles ax,i = (1/4 - 4 + xi /c, 1/2 + 4 - xi /c) and ax,i = (1/4 + 4 - xi /c, 1/2 - 4 + xi /c) For each element in yi  Y we define two rectangles ay,i = (1/4 - 3 + yi /c, 1/2 + 3 - yi /c) and ay,i = (1/4 + 3 - yi /c, 1/2 - 3 + yi /c) For each element in zi  Z we define two rectangles az,i = (1/4 - 2 + zi /c, 1/2 + 2 - zi /c) and az,i = (1/4 + 2 - zi /c, 1/2 - 2 + zi /c) Let Ax = {ax,1 , . . . , ax,q } and Ax = {ax,1 , . . . , ax,q }. Ay , Ay , Az and Az are defined similarly to be the set of rectangles ay,i , ay,i , az,i and az,i respectively. We will use A to denote the collection Ax  Ay  Az and A = Ax  Ay  Az . Next for each tl  T we define two rectangles bl and bl such that bl = (1/4 + 8 + tl /c, 1/2 +  - tl /c) and bl = (1/4 - 8 - tl /c, 1/2 -  + tl /c). Let B = {b1 , . . . , b|T | } and B = {b1 , . . . , b|T | }. Finally we define D to be a collection of |T | - q dummy rectangles di such that di = (3/4 - 10, 1). We say that two rectangles a and a are buddies iff {a, a } is {ax,i , ax,i } or {ay,j , ay,j } or {az,k , az,k } for 1  i, j, k  k or {a, a } = {bl , bl } for some 1  l  |T |. From the values chosen for the sizes of the rectangles it is easy to see that, Observation 1. For each rectangle a  A  A , w(a) + h(a) = 3/4. For any two buddies b  B and b  B , w(b) + h(b) + w(b ) + h(b ) = 3/2. Observation 2. For any two rectangles a, a in A  A  B  B , h(a) + h(a ) = 1 iff a and a are buddies. The following definition is needed only for the next two lemmas. For a rectangle a, we now define (a) which allows us to relate back the rectangle to the integers xi , yj , zk or bl . For a rectangle ax,i  Ax , let (ax,i ) = xi . Similarly, (ay,j ) = yj , (az,k ) = zk , (bl ) = tl and (ax,i ) = -xi ,(ay,j ) = -yj , (az,k ) = -zk , (bl ) = -tl .

3 10 + 15. Considerthat i=1 (ai ) + (b) =  c = r 3 ing the quantity i=1 (ai ) + (b) mo dulo r , it follows that there is exactly one rectangle each from Ax , Ay , Az and B since 15 = 1 + 2 + 4 + 8 and this is the only way to represent 15 as a sum of four numbers from the set {1, 2, 4, 8}. Next, considering the sum 3 23 9 i=1 (ai ) + (b) again mo dulo r , r , . . . , r , it follows that {a1 , a2 , a3 , b} = {ax,i , ay,j , az,k , bl } such that tl = (xi , yj , zk ) is a tuple in the MAX-3-DM problem. Lemma 2.2. Let R = {a1 , a2 , a3 , a4 } be four rectangles lying in A  A , such that no two of thei e are buddies. s Then for any choice of ai , 1  i  4, w(ai ) = 1. Proof. Suppose for the sake of contradiction that 4 i=1 w (ai ) = 1. As 0  |(ai )|   c/10, it must b e 4 that i=1 (ai ) = 0. We first show that there cannot be more then one rectangle from Ax  Ax in the set R (later we will show that same argument works for Ay  Ay and Az  Az , thus giving a contradiction). Consid4 ring the coefficient of r and r3 in the sum quantity e i=1 (ai ). These co efficients dep end on rectangles in (Ax  Ax )  R only. Let i1 , i2 , i3 , i4 denote the indices of rectangles from (Ax  Ax )  R (where an index is 0, if fewer than 4 occur). Since no two rectangles are buddies, we cannot have both ax,ik and ax,ik in R. So, for each ik , 1  k  4, we associate a variable (ik ), where (ik ) = 1 if ax,ik  R and -1 if ax,ik  R. Since the coe4 cients of r and r3 s4 m to 0, we must have ffi u that k=1 (ik )ik = 0 and k=1 (ik )i2 = 0, with the k constraints that all positive ik 's are distinct. We now claim that the only feasible solution to the above system is ik = 0 for all 1  k  4. Clearly we need at leak t 3 of the ik 's to be positive else we cannot have s (ik )ik = 0. Second, note that all (ik ) can not be -1 or +1. Under these constraints, when exactly three are non-zero ik 's, we have the equations, i1 + i2 = i3 and i2 + i2 = i2 under the constraints that all numbers 1 2 3 are positive and distinct. But clearly, there can be no solution to this. In the case when all the ik 's are positive by renaming variables all cases can be reduced to the following two cases: 1. i1 + i2 = i3 + i4 and i2 + i2 = i2 + i2 , 1 2 3 4

Lemma 2.1. For any three rectangles a1 , a2 , a3  A 2. i1 + i2 + i3 = i4 and i2 + i2 + i2 = i2 . 1 2 3 4 and b  B , w(a1 ) + w(a2 ) + w(a3 ) + w(b) = 1 iff {a1 , a2 , a3 , b} = {ax,i , ay,j , az,k , bl } such that tl = The last case clearly does not have a solution. For the (xi , yj , zk ) is a tuple in the MAX-3-DM problem. first case, rewrite the equations as i1 - i3 = i4 - i2 and i2 - i2 = i2 - i2 , which implies that i1 + i3 = i4 + i2 , and 1 3 4 2 Proof. The "if" direction follows directly from defini- hence i1 = i4 which gives a contradiction. Repeating tions. We now proof the "only if" part of the lemma. the argument identically for Ay  Ay and Az  Az the As 0 < (ai ) <  c/10, for 1  i  3 and 0 < (b) <  c, result follows. then if w(a1 ) + w(a2 ) + w(a3 ) + w(b) = 1, it must be

198


Observation 3. The width (resp. height) of any rectangle in the instance is at least 1/4 - 10 (resp. at least 1/2 - 5 ), and hence the area of any rectangle is at least 1/8 - 25/4 > 1/9. Thus no bin can have more than 8 rectangles. Observation 4. If we consider a feasible bin packing as a packing of some unit square with the left lower corner in the origin and right upper corner in the point (1, 1) then any vertical line, i.e. a line paral lel to the y axis, intersects at most one rectangle from A  B since height of each rectangle in A  B is strictly greater than 1/2. This observation implies that any bin can contain at most 4 rectangles in A  B , and at most 3 rectangles in B since the width of each rectangle in A  B more than 1/5, and the width of each rectangle in B is more than 1/4. Finally, it is easy to see that,

1
y=4/5 (L_2)

A'(x,i)

A'(y,j)

A'(z,k)

B'(l)

1/2

A(x,i)
y=1/5 (L_1)

A(y,j)

A(z,k)

B(l)

0

1/4

1/2

3/4

1

Observation 5. If a rectangle di  D lies in some bin Figure 1: Packing of the rectangles corresponding to a S , then S contains at most 2 other rectangles and at triple most one of them is a rectangle from A  B . Given a packing of the bins, call a bin good if it contains intersect exactly one of L1 or L2 . This follows as any exactly 8 rectangles and moreover it has exactly 4 rectangle has height at most 1/2 + 1/50 < 3/5 and at rectangles from A  B . The following crucial lemma least 1/2 - 1/50 > 2/5. Moreover, as any rectangle has characterizes the structure of good bins. width strictly more than 1/5, it follows that each L1 and L2 intersect exactly 4 rectangles. Let {a1 , a2 , a3 , a4 } Lemma 2.3. A bin is good if and only if it contains the rectangles ax,i , ay,j , az,k , bl and the corresponding denote the rectangles that intersect L1 such that ai is rectangles ax,i , ay,j , az,k , bl such that tl = (xi , yj , zk ) to the left of aj for i < j . Similarly let {a5 , a6 , a7 , a8 } denote the rectangles that intersect L2 in the left to corresponds to a triple in MAX-3-DM instance. right order. Thus we have that Proof. We first show that the rectangles corresponding i4 to a triple can be packed in a bin. Starting from the (2.1) w(ai )  1 bottom left corner of the bin and moving towards the =1 right, we pack the rectangles ax,i ,ay,j , az,k and bl . Each of these rectangles is placed such that it touches the and that i4 bottom of the bin. Figure 1 shows the packing. It is (2.2) w(ai+4 )  1 easy to verify that these four rectangles can be packed =1 as described, as w(ax,i ) + w(ay,j ) + w(az,k ) + w(bl ) = 1 -  + xi + yj + zk + tl = 1. Next we observe that each of Finally observe that for each 1  i  4 each rectangle the rectangles ax,i , ay,j , az,k and bl can be placed in the ai must overlap with ai+4 in an x - coordinate. Thus remaining gaps (as shown in Figure 1). Clearly, ax,i can we have the constraints that be placed on top of ax,i because h(ax,i ) + h(ax,i ) = 1 and h(ai ) + h(ai+4 )  1 for 1  i  4 as h(ax,i ) < h(ay,j ) < h(az,k ) < h(bl ), this allows ax,i to (2.3) extend horizontally beyond ax,i . Arguing similarly and We consider three cases depending on the number of observing that w(ax,i ) + w(ay,j ) + w(az,k ) + w(bl ) = 1, rectangles in B that lie in the bin. it is easy to see that rectangles ay,j , az,k and bl also fit. 1. At least 2 rectangles in B lie in the bin: Since each We now show that any good bin must correspond to bin in B has width at least 1/4 + 8 , two such bins a triple. We first give a way for labeling the 8 rectangles use at least 1/2 + 16 . Thus the width left for in a good bin. Consider the lines L1 = {y = 1/5} bins from A is at most 1/2 - 16 (we cannot put and L2 = {y = 4/5}. It is easy to see that any in rectangles from A on top of the rectangles from packing of a bin with 8 rectangles, each rectangle must

199


B), and hence at most 1 bin from A can fit. Thus the bin can have at most 3 rectangles from A  B and hence cannot be good. Similarly, if 3 rectangles from B lie in the bin, there cannot be any rectangle from A. 2. No rectangle in B lies in the bin: We claim the bin cannot have more than 3 rectangles from A. For the sake of contradiction suppose r1 , r2 , r3 , r4  A lie in the bin. Then no rectangle from B can lie in the bin, because any rectangle in A has height at least 1/2 + 2 while the height of any rectangle in B is at least 1/2 -  and moreover any rectangle in B must overlap in some x-coordinate with some ri for 1  i  4. Thus all the 8 rectangles lie in A  A . Adding Equations 2.1, 2.2 and 2.3 we 8 have that i=1 (w(ai ) + h(ai ))  6. Moreover from 8 Observation 1 we have that i=1 (w(ai ) + h(ai )) = 6, thus it must be the case that each of Equations 2.1,2.2 and 2.3 must hold with an equality. By Observation 2, this implies that ai and ai+4 are buddies for each i = 1, . . . , 4. This in particular implies that among the rectangles a1 , a2 , a3 and a4 no4two are buddies. Therefore, it is impossible that i=1 w (ai ) = 1 by Lemma 2.2, and hence we have a contradiction. 3. Exactly one rectangle bl  B lies in the bin: In the case we will show that if the bin is good, then it must correspond to a triple tl = (xi , yj , zk ). Suppose the bin is good, then there are exactly three other rectangles from A. Since any rectangle from B cannot overlap in an x-coordinate with any rectangle in A, it follows that there can be at most one rectangle from B , which must overlap with bl . Next, we show that there has to be at least one rectangle from B . Suppose there are no rectangles from B , then we claim that the total width of all the rectangles must be strictly more than 2, which is not possible. To see this, since there is no rectangle from B , there must be four rectangles from A . As the width of any rectangle in A (resp. B ) is strictly more than 1/4 +  (resp. 1/4 + 8 ), this takes up width > 5/4 + 12 . But, as the width of any rectangle in A is at least 1/4 - 4 , we do not have sufficient total width to pack 3 rectangles from A. This proves the claim. Hence there is exactly one rectangle from B . Call it bl . Since bl can only overlap vertically with bl it must be that h(bl ) + h(bl )  1, and hence that w(bl ) + w(bl )  1/2. Moreover, by Observation 1, w(bl ) + h(bl ) + h(bl ) + w(bl ) = 3/2. Now, by summing Equations 2.1,2.2 and 2.3 and using Observation 1 we have that each inequality in

Equations 2.1,2.2 and 2.3 is satisfied with equality. To complete the argument, suppose bl intersects w line L1 , let a1 , a2 , a3 denote the rectangles in A  A hich also intersect L1 . Thus, we have that w(a1 )+ w(a2 ) + w(a3 ) + w(bl ) = 1. None of the ai , 1  i  3 can lie in A , because otherwise it is always the case that w(a1 ) + w(a2 ) + w(a3 ) + w(bl ) > 1. Since all a1 , a2 and a3 lie in A, by Lemma 2.1 it follows that these rectangles correspond to a triple tl = (xi , yj , zk ). Theorem 2.1. There is no Asymptotic PTAS for the 2-Dimensional Bin Packing Problem unless P = N P . Proof. If the MAX-3-DM problem has a matching consisting of q tuples, then we can get a bin packing solution which uses |T | bins as follows. For each of the tuples in the matching, create a good bin as described in Lemma 2.3. For each tl not in the matching, we put bl and bl along with a dummy rectangle, and hence we use q + (|T | - q ) = |T |  3q bins. Assume now that every feasible solution of the MAX-3-DM problem has at most (1 - )q triples. We will show that any solution to the corresponding bin packing problem uses at least (1 + /33)|T | bins. Consider any feasible solution to the bin-packing instance. There will be exactly nd = |T | - q bins with dummy ob jects. Lemma 2.3 implies that if a bin is not good then it either has at most 7 rectangles or else it has at most 3 rectangles from A  B . Let ng denote the number of good bins. Since the set of good bins corresponds to some feasible solution by Lemma 2.3 we have ng  (1 - )q . Among the bins which are not good let nb1 denote the number of bins (other than the bins with dummy ob jects) which contain at most 7 rectangles and let nb2 denote the rest of the bins, (note that these are precisely the bins that have eight rectangles but 3 or fewer rectangles from A  B ). Since any solution must cover all the rectangles in A  B and any bin with a dummy rectangle can have at most one rectangle from A  B , we have the constraint that 4ng + 4nb1 + 3nb2 + nd  3q + |T | Equivalently, 4ng + 4nb1 + 3nb2  4q Similarly, since all the rectangles must be covered, we have that 8ng + 7nb1 + 8nb2 + 2nd  6q + 2|T | Equivalently, 8ng + 7nb1 + 8nb2  8q

200


Adding the equations above, 12ng + 11nb1 + 11nb2  12q . Equivalently, ng + nb1 + nb2  12q /11 - ng /11. Adding the bins with dummy ob jects, this implies that the total number of bins used is at least |T | - q + 12q /11 - ng /11 = |T | + (q - ng )/11  |T | + q /11  |T |(1 + /33). Now if there is an APTAS for 2-dimensional bin packing, then for every > 0, there exists an algorithm A and a constant c , such that for instances I if |Opt(I )| > c , th w en A  (1 + 2 )|Opt(I)|. Thus for any > 0, if q > c e can distinguish between two instances of the MAX3-DM problem with |T | = q and |T |  (1 - 66)q , which is an NP-hard problem by [17] 3 PTAS for square packing In this section we give a PTAS for the special case where we want to pack squares into bins. We begin with some notation and definitions: The problem instance I is a collection of squares specified by their sizes. For any collection of squares C , we use A(C ) to denote the total area of the squares in C , and OP T (C ) is used to denote the optimum number of unit size bins used to pack the squares in C . Before describing our overall algorithm, we first describe a subroutine (known as the Decreasing height shelf algorithm) that we use to pack squares in an arbitrary rectangular region. A shelf is a row of items having their bases on a line which is either the base of the bin or the line drawn at the top of the tallest item packed in the shelf below. Given a collection C such that the square indexed by i has size si × si and s1  s2  . . .  sn which are to be packed in a rectangular region R, the Decreasing Height Shelf algorithm is defined as follows: Starting with a packing of s1 in the bottom left corner of R, continue packing ob jects s2 , . . . , si1 at the base of R such that si1 +1 does not fit. At this point, we close this shelf with a vertical line L1 at height s1 . We open a new shelf with line L1 as the base, and continue packing ob jects si1 +1 , . . . , si2 and so on. If after k shelves, the item sik +1 does not fit in the shelf above (i.e. we do not have enough space to begin the (k + 1)th shelf, we close the rectangle R and do not pack any more ob jects in it. This algorithm was described and studied first in [5]. The following is a crucial property of the decreasing height shelf algorithm. Lemma 3.1. Let Cs be an arbitrary col lection of squares, where each square has size at most s. Let R be a rectangular region of size a × b (means width a and height b), in which Cs is to be packed. Assume that the col lection Cs is large enough that it never runs out of squares while packing R. Then, packing the squares in Cs according to the decreasing height shelf heuristic wastes at most s(a + b) area. Proof. Let si denote the size of job starting shelf i, and

li denote size of the last job in shelf i. The waste at the end of this shelf is at most si+1 si (because si+1 could not fit in this shelf. The waste at the top of each shelf (excluding the area already accounted for) is at most (si - li )(a - si+1 ). Suppose there are k shelves. The waste in the region where we could not begin the k +1th shelf is at most (lk )a. Adding up all this k waste we get, lk a + i=1 (si - li )a + li si+1 . Observing that si  li  si+1 , this waste is upper bounded by k s1 a + i=1 li s1  s1 (a + b) Corollary 3.1. While packing squares in a unit square bin, Decreasing height shelf heuristic is a 6 approximation with respect to the area. Proof. Suppose the largest square has size at least   1 2 - 1, then we pack at least ( 2 - 1)2 > /6 of the area. If the largest square is smaller han 2 - 1, by t the above lemma e waste at most 2( 2 - 1) and hence w use at least 3 - 2 2 > 1/6. Let 0 = 1 > 1 > 2 > . . . > k = 0 be a sequence i of numbers, where k = 1/ and i = 2 -1 . Note that i = 2-1 , for 1  i  k - 1. Let Ii denote the subi collection of squares in I whose sizes lie in the range [ i-1 , i), for 1  i  k . Observe that the Ii partition I into a collection of k disjoint sets. Thus, there exists some m such that A(Im )  A(I). We call all squares in Im as medium, squares in Ii such that i < m are called large, and squares in Ii for i > m are called small. This definition is due to Sevastianov and Woeginger [19] and is very helpful in design of PTAS-es for scheduling and packing problems. We now describe our algorithm. The algorithm will have 3 phases: In the first phase we pack the medium squares. In the second phase we find a close to optimum packing of the large squares, and in the final phase we pack the small squares. We now describe each of these phases. Packing medium squares: Take the medium squares and pack them in separate bins using the Decreasing height shelf algorithm. These bins are closed and will never be used again. Packing large squares: Let L denote the set of large ob jects. Let l = |L| and s1  . . .  sl denote the sizes of the squares in L. We form g = 1/ m groups as follows. The first group L1 , consists for largest l/g pieces the second of the next largest l/g and so on. Construct a new instance L obtained by discarding the first group and for each other group, rounding the size of the square to the size of the largest square in this group. Note that OP T (L )  OP T (L). This rounding trick is due to Fernandez de la Vega and Lueker [8] and is very popular in bin packing literature. Our algorithm packs each square in L1 in its own separate bin. To obtain a

201


packing of L2  . . .  Lg , we will obtain a packing of L . Clearly, a valid packing of L can be used to pack the squares in L2  . . .  Lg . Notice that the instance L has at most g distinct job sizes, call them s1 , . . . , sg . We now show how to obtain a close to optimum packing of L . The ideas are similar to that of one dimensional bin packing [8]. Consider the ways in which a single bin can be packed. These can be described by a k -tuple t = (t1 , . . . , tg ), where ti denote the number of squares of size si in the bin. Since each large square has size at least m-1 , the total number of such squares in any bin can be at most 1/ 2 -1 . Thusg the number , m  of all possible tuples can be at most
+ 1 / m- 1 2 g
m 2g+1/ 2 -1  22g which is a constant. Call a tuple T = (t1 , . . . , tg ) feasible, if there is a way to pack all the ob jects corresponding to t in a single bin. It is easy to check if a tuple is feasible in constant time. For every square packed in a bin we can assume that it is shifted to leftmost and bottom most position which implies that each of the lower left corner coordinates of this square can be represented as a sum of constant number of square sizes. The algorithm first figures out in constant time the set of all feasible tuples. Let T = {T1 , . . . , Tq } denote the set of all feasible tuples. Let Tij denote the number of squares of size tj in Ti . We form a linear program (denoted by LP) as follows:

or the boundary of the bin B . This divides the gaps in the bin into rectangular regions. See figure 2. Moreover, the number of such rectangular regions is at most 4/ 2 -1 + 1. This follows by adding the lines one by one. m Since there are at most 1/ 2 -1 squares in a bin, we have m at most 4/ 2 -1 such lines and each line adds at most m one additional rectangular region. To pack the small ob-

Regions where smalls are placed

Figure 2: Regions where smal l squares are packed jects, consider the rectangular regions in any arbitrary order, and pack the small ob jects in these regions according to the decreasing height shelf algorithm. If all the small ob jects cannot be packed in the rectangular regions, open additional new bins to pack the remaining small ob jects. Again, the small ob jects in the new bins are packed according to the decreasing height shelf algorithm. Theorem 3.1. The algorithm described above is an asymptotic PTAS for square packing in two dimensions.

(3.4) sub ject to iq
=1

min

iq
=1

xi

Tij xi xi

 nj ,  0,

for each j = 1, . . . , g for each i = 1, . . . , q

Proof. By Corollary 3.1, the number of bins Nm used for the medium sized squares is at most 6A(Im ), since The variable xi corresponds to the (fractional) number A(Im )  A(I), we have that of bins which have configuration corresponding to the tuple Ti . Observing that any basic optimal solution (3.5) Nm  6A(Im )  6 A(I)  6 OP T (I ) to this LP has at most g non-zero variables xi . We can obtain an integral solution by simply rounding We now account for the number of bins used by the each non-zero xi to next integer. This increases the large squares. Since each large square has size at cost by at most g . After that we define xi packings least m-1 and hence area at least 2 , we have that m-1 corresponding to the tuple i this guarantees that for OP T (I )  OP T (L)  l 2 . The number of bins used m-1 every size type there is enough squares used in that by our algorithm to pack the ob jects in L1 is packing and therefore all large squares can be packed. Packing Small Squares: Consider the bins con- (3.6) l/g  ml + 1 = m-1 l + 1  OP T (I ) + 1 2 taining the large ob jects in an arbitrary order. For each bin we first divide the gaps into rectangular shapes us- Next, as LP (L )  OP T (L ), I P (L )  LP (L ) + g and ing the following procedure: Fix a bin B . For each as OP T (L )  OP T (L)  OP T (I ) we have that square in B extend its top side and bottom side horizontally in both directions until it hits another square (3.7) I P (L )  OP T (I ) + g

202


By Equations 3.6 and 3.7 it follows that the total number of bins used by our algorithm to pack the large ob jects is at most (3.8) (1 + )OP T (I ) + g + 1

If no additional bins are opened for the small squares, the result follows from Equations 3.5 and 3.8. If additional bins need to be opened for the small squares, consider the total amount of area wasted in the bins containing the large squares. Note that the size of the small squares is at most m, and hence by Lemma 3.1 the total area in any rectangular region of dimensions a × b is at most m(a + b)  2 m. Since there were at most 8/ 2 -1 such regions that each such bin has waste m at most 2 m · 8/ 2 -1  16 S m imilarly, the area wasted in the bins in which only small squares are packed (expect for one bin) is trivially upper bounded by 16 . Thus the total number of bins used in this case is  A(I )/(1 - 16 ) + 1 + 6 A(I)  A(I )(1 + O( )) + 1 for sufficiently small. Thus the result follows. A(I )/(1 - 16 ) + 1 + Nm

Extension to the d-dimensional case: The above algorithm can extends directly to yield an APTAS in the d-dimensional case for fixed d. The only difference is that we choose 0 = 1 and i = d-1 for 1  i  k - 1 i and k = 1/ . It is easy to see that the algorithm for d = 2 described above gives an APTAS for this case. References
[1] A. Caprara. Packing 2-dimensional bins in harmony. In Foundations of Computer Science, pages 490­499, 2002. [2] C. Chekuri and S. Khanna. On multi-dimensional packing problems. In Symposium on Discrete Algorithms (SODA), pages 185­194, 1999. [3] 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. [4] E.G. Coffman, M.R. Garey, and D.S. Johnson. Approximation algorithms for bin packing: a survey. In D. Hochbaum, editor, Approximation algorithms for NPhard problems, pages 46­93. PWS Publishing, Boston, 1996. [5] E. G. Coffman, M. R. Garey, D. S. Johnson and R. E. Tarjan. Performance bounds for level-oriented two dimensional packing algorithms. SIAM J. Computing 9 (1980), pages 808-826.

[6] J. R. Correa and C. Kenyon. Approximation schemes for multidimensional packing. These proceedings. [7] J. Crisik and G. Woeginger. On-line packing and covering problems. In Online Algorithms: The State of the Art, editors A. Fiat and G. Woeginger, pages 147­177, 1998. [8] W. Fernandez de la Vega and G. Lueker. Bin packing can be solved within 1 +  in linear time. Combinatorica, 1:349­355, 1981. [9] L. Epstein and R. Van Stee. Optimal online bounded space multidimensional packing. These proceedings. [10] C. E. Ferreira, F. K. Miyazawa, and Y. Wakabayashi. Packing squares into squares. Pesquisa Operacional, 19(2):223­237, 1999. [11] K. Jansen and G. Zhang. On rectangle packing: maximizing benefits. These proceedings. [12] V. Kann. Maximum bounded 3-dimensional matching is MAX SNP-complete. Information Processing Letters, 37:27­35, 1991. [13] N. Karmarkar and R. M. Karp. An efficient approximation scheme for the one-dimensional bin-packing problem. In Foundations of Computer Science (FOCS), pages 312­320, 1982. [14] Claire Kenyon and Eric Remila. Approximate strip packing. In Foundations of Computer Science (FOCS), pages 31­36, 1996. [15] Y. Kohayakawa, F.K. Miyazawa, P. Raghavan, and Y. Wakabayashi. Multidimensional cube packing. In Brazilian Symposium on Graphs, Algorithms and Combinatorics, 2001. [16] 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 Paral lel and Distributed Computing, 10: 271-275, 1990. [17] E. Petrank. The hardness of approximation: gap location. Computational Complexity, 4:133­157, 1994. [18] S. Seiden and R. van Stee. New bounds for multidimensional packing. Algorithmica, 36(3):261­293, 2003. [19] S. Sevastianov and G. Woeginger. Makespan minimization in open shops: a polynomial time approximation scheme. Networks and matroids; Sequencing and scheduling. Math. Programming, 82, no. 1-2, Ser. B:191­198, 1998. [20] G. Woeginger. There is no asymptotic PTAS for twodimensional vector packing. Information Processing Letters, 64:293­297, 1997.

203