Optimal Online Bounded Space Multidimensional Packing Leah Epstein Abstract We solve an open problem in the literature by providing an online algorithm for multidimensional bin packing that uses only bounded space. To achieve this, we introduce a new technique for classifying the items to be packed. We show that our algorithm is optimal among bounded space algorithms for any dimension d > 1. Its asymptotic performance ratio is ( )d , where 1.691 is the asymptotic performance ratio of the one-dimensional algorithm H A R M O N I C. A modified version of this algorithm for the case where all items are hypercubes is also shown to be optimal. Its asymptotic performance ratio is sublinear in d. Additionally, for the special case of packing squares in two-dimensional bins, we present a new unbounded space online algorithm with asymptotic performance ratio of at most 2.271. We also present an approximation algorithm for the offline problem with approximation ratio of 16/11. 1 Introduction Bin packing is one of the oldest and most well-studied problems in computer science [11, 6]. The study of this problem dates back to the early 1970's, when computer science was still in its formative phase--ideas which originated in the study of the bin packing problem have helped shape computer science as we know it today. The influence and importance of this problem are witnessed by the fact that it has spawned off whole areas of research, including the fields of online algorithms and approximation algorithms. In this paper, we study a natural generalization of bin packing, called box packing. Rob van Stee 0 xi (p) and xi (p) + si (p) 1 for 1 i d. Further, the positions must be assigned in such a way that no two items in the same bin overlap. A bin is empty if no item is assigned to it, otherwise it is used. The goal is to minimize the number of bins used. Note that for d = 1, the box packing problem reduces to exactly the classic bin packing problem. There are a number of variants of this problem which are of interest: · In the online version of this problem, each item must be assigned in turn, without knowledge of the next items. · In the hypercube packing problem we have the restriction that all items are hypercubes, i.e. an item has the same size in every dimension. · In the bounded space variant, an algorithm has only a constant number of bins available to accept items at any point during processing. The bounded space assumption is a quite natural one, especially so in online box packing. Essentially the bounded space restriction guarantees that output of packed bins is steady, and that the packer does not accumulate an enormous backlog of bins which are only output at the end of processing. School of Computer Science, The Interdisciplinary Center, Herzliya, Israel. lea@idc.ac.il. Research supported by Israel Science Foundation (grant no. 250/01). Centre for Mathematics and Computer Science (CWI), Amsterdam, The Netherlands. Rob.van.Stee@cwi.nl. Research supported by the Netherlands Organization for Scientific Research (NWO), project number SION 612-061-000. The offline versions of these problems are NP-hard, while even with unlimited computational ability it is impossible in general to produce the best possible solution online. We therefore consider both online and offline approximation algorithms. The standard measure of algorithm quality for box packing is the asymptotic performance ratio, which we now deProblem Definition: Let d 1 be an integer. In the d- fine. For a given input sequence , let costA ( ) be the numdimensional box packing problem, we receive a sequence ber of bins used by algorithm A on . Let cost( ) be the of items p1 , p2 , . . . , pn . Each item p has a fixed size, which minimum possible number of bins used to pack items in . is s1 (p) × · · · sd (p). I.e. si (p) is the size of p in the ith The asymptotic performance ratio for an algorithm A is dedimension. We have an infinite number of bins, each of fined to be which is a d-dimensional unit hyper-cube. Each item must c c . ostA ( ) be assigned to a bin and a position (x1 (p), . . . , xd (p)), where RA = lim sup sup ost( ) = n cost( ) n Let O be some class of box packing algorithms (for instance online algorithms). The optimal asymptotic performance ratio for O is defined to be R = inf AO R . Given O , O A our goal is to find an algorithm with asymptotic performance ratio close to R . O 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 214 Previous Results: The classic online bin packing problem was first investigated by Ullman [26]. He showed that 17 the F I R S T F I T algorithm has performance ratio 10 . This result was then published in [16]. Johnson [17] showed that the N E X T F I T algorithm has performance ratio 2. Yao showed that R E V I S E D F I R S T F I T has performance ratio 5 , 3 and further showed that no online algorithm has performance 3 ratio less than 2 [31]. Brown and Liang independently improved this lower bound to 1.53635 [3, 22]. The lower bound currently stands at 1.54014, due to van Vliet [27]. Define i+1 = i (i - 1) + 1, and = i 1 = 2, =1 1 1.69103. i - 1 Lee and Lee presented an algorithm called H A R M O N I C, which uses m > 1 classes and uses bounded space. For any > 0, there is a number m such that the H A R M O N I C algorithm that uses m classes has a performance ratio of at most (1 + ) [20]. They also showed there is no bounded space algorithm with a performance ratio below . Bounded space algorithms for bin packing were also considered by Woeginger in [30], and by van Vliet in [29]. Currently the best known unbounded space upper bound is 1.58889 due to Seiden [24]. Offline bin packing has also received a great deal of attention, for a survey see [6]. The most prominent results are as follows: Garey, Graham and Ullman [16] were the first to study the approximation ratios of both online and offline algorithms. Fernandez de La Vega and Lueker [12] presented the first approximation scheme for bin packing. Karmarkar and Karp [18] gave an algorithm which uses at most cost( ) + log2 (cost( )) bins. While box packing is a natural next step from bin packing, the problem seems to be more difficult, and the number of results is smaller. The offline problem was introduced by Chung, Garey and Johnson [5]. Caprara [4] presented an algorithm with approximation ratio . The online problem was first investigated by Coppersmith and Raghavan [7], who give an algorithm based on N E X T F I T with performance ratio 143 = 3.25 for d = 2. Csirik, Frenk and Labbe [9] give an algorithm based on 49 F I R S T F I T with performance ratio 16 = 3.0625 for d = 2. Csirik and van Vliet [10] present an algorithm with performance ratio ( )d for all d 2 (2.85958 for d = 2). Even though this algorithm is based on H A R M O N I C, it was not clear how to change it to bounded space. Li and Cheng [21] also gave a H A R M O N I C-based algorithm for d = 2 and d = 3. Seiden and van Stee [25] improve the upper bound for d = 2 to 2.66013. Several lower bounds have been shown [14, 15, 28, 2]. The best lower bound for d = 2 is 1.907 [2], while the best lower bound for large d is less than 3. For bounded space algorithms, a lower bound of ( )d is implied by [10]. For online square packing, even less is known. The following results are known for d = 2: Coppersmith and Raghavan [7] show an upper bound of 43/16 = 2.6875 and a lower bound of 4/3. The upper bound is improved to 395/162 < 2.43828 by Seiden and van Stee [25]. For d = 3, Miyazawa and Wakabayashi [23] show an upper bound of 3.954. For the offline problem, Ferreira, Miyazawa and Wakabayashi give a 1.988-approximation algorithm [13]. This was improved to 14/9 by Kohayakawa et al. [19] and Seiden and van Stee [25] independently. However, the result in [19] is more general in that the authors give two approximation algorithms for any dimension d 2 with asymptotic performance bounds of 2-(1/2)d and 2-(2/3)d . Finally, the algorithm in [4] is shown to have an approximation ratio in (1.490, 1.507) for this problem, if a certain conjecture holds. Our Results: In this paper, we present a number of results for online and offline box and square packing: · We begin by presenting a bounded space algorithm for the packing of hypercubes. An interesting feature of the analysis is that although we show the algorithm is optimal, we do not know the exact asymptotic performance ratio. The asymptotic performance ratio is (log d) and O (d/ log d). · We then extend this algorithm to a bounded space algorithm for general hyperbox packing and show that this algorithm is also optimal, with a asymptotic performance ratio of ( )d . This solves the ten-year old open problem of how to pack hyperboxes using only bounded space. · We present a new unbounded space algorithm for two dimensional square packing with a asymptotic performance ratio of 2.2709, which cannot be attained by a bounded space algorithm. · We improve the approximation algorithm for square packing from [25] and show that the resulting algorithm has an approximation ratio of at most 16/11 < 1.45455. Independently and in parallel, Bansal and Sviridenko [1] and Correa and Kenyon [8] presented approximation schemes for this problem. For the online results, we will use the technique of weighting functions. This technique was originally introduced for one-dimensional bin packing algorithms [26]. In [25], it was demonstrated how to use the analysis for onedimensional algorithms to get results for higher dimensions. In contrast, in the current paper we will define weighting 215 functions directly for multidimensional algorithms, without using one-dimensional algorithms as subroutines. New Technique: To construct the bounded space algorithm we adapt some of the ideas used in previous work. Specifically, the algorithm of [10] also required a scheme of partitioning bins into sub-bins, and of sub-bins into smaller and smaller sub-bins. However, in order to keep a constant number of bins active, we had to introduce a new method of classifying items. Our key improvement is that there is not one single class of "small" items like all the standard algorithms have, but instead we partition the items into an infinite number of classes that are grouped into a finite number of groups. The hypercube packing algorithm uses an easier scheme for the same purpose. This is a more direct extension of the method used in [7]. 2 An optimal algorithm for bounded space packing of hypercubes In this section we define the algorithm for hypercubes, denoted by A L G . In the next section we extend it to deal with hyperboxes. Let the size of hypercube q , s(q ) be the length of each side of the hypercube. The algorithm has a parameter > 0. Let M 10 be an integer parameter such that M 1/(1 - (1 - )1/(d+1) ) - 1. We distinguish between "small" hypercubes (of size smaller or equal to 1/M ) and "big" hypercubes (of size larger than 1/M ). The packing algorithm will treat them in different ways. All large hypercubes are packed using a multidimensional version of H A R M O N I C [20]. The hypercubes are assigned a type according to their size: type i items have a size in the interval (1/i + 1, 1/i] for i = 1, . . . , M - 1. The bins that are used to pack items of these types all contain items of only one type. We use the following algorithm to pack them. A bin is called active if it can still receive items, otherwise it is closed. Algorithm A S S I G N L A R G E(i) At all times, there is at most one active bin for each type. Each bin is partitioned into id hypercubes (sub-bins) of size 1/i each (the sub-bins create a grid of i strips in each dimension). Each such sub-bin can contain exactly one item of type i. On arrival of a type i item it is assigned to a free sub-bin (and placed anywhere inside this sub-bin). If all sub-bins are taken, the previous active bin is closed, a new active bin is opened and partitioned into sub-bins. The small hypercubes are also assigned types depending on their size, but in a different way. Consider an item q of size s(q ) 1/M . Let k be the largest non-negative integer such that 2k s(q ) 1/M . Clearly 2k s(q ) > 1/(2M ). Let i be the integer such that 2k s(q ) (1/i + 1, 1/i], i {M , . . . 2M - 1}. The item is defined to be of type i. Each bin that is used to pack small items contains only small items with a given type i. Note that items of very different sizes may be packed together in one bin. We now describe the algorithm to pack a new small item of type i for i = M , . . . , 2M - 1. A sub-bin which received a hupercube is said to be used. A sub-bin which is not used and not cut into smaller sub-bins is called empty. Algorithm A S S I G N S M A L L(i) The algorithm maintains a single active bin. Each bin may during its use be partitioned into sub-bins which are hypercubes of different sizes of the form 1/(2j i). When an item q of type i arrives we do the following. Let k be the integer such that 2k s(q ) (1/i + 1, 1/i]. 1. If there is an empty sub-bin of size 1/(2k i), then the item is simply assigned there and placed anywhere within the sub-bin. 2. Else, if there is no empty sub-bin of any size 1/(2j i) for j > k inside the current bin, the bin is closed and a new bin is opened and partitioned into sub-bins of size 1/i. Then the procedure in step 3 is followed, or step 1 in case k = 0. 3. Take an empty sub-bin of size 1/(2j i) for a minimum j > k . Partition it into 2d identical sub-bins (by cutting into two identical pieces, in each dimension). If the resulting sub-bins are of size larger than 1/(2k i), take one of them and partition it in the same way. This is done until sub-bins of size 1/(2k i) are reached. The new item is assigned into one such sub-bin. Finally, the main algorithm only determines the type of newly arriving items and assigns them to the appropriate algorithms. The total number of active bins is at most 2M - 1. In order to perform a competitive analysis, we prove the following claims. C L A I M 1 . For a given i M , consider an active bin. At all times, the number of empty sub-bins of each size except 1/i is at most 2d - 1. Proof. Note that the number of empty sub-bins of size 1/i decays from id to zero during the usage of the bin. Consider a certain possible size r of a sub-bin. When a sub-bin of some size r is created, it is due to partition of a larger sub-bin. This means that there were no empty sub-bins of size r before the partition. Afterwards, there are at most 2d - 1 of them for each size that has been created during the partitioning (for the smallest size into which the sub-bin is partitioned, 2d sub-bins created, but one is immediately used). C L A I M 2 . For a given i M , when a bin is about to be closed, the total volume of empty sub-bins in the bin is at most 1/id . 216 item p of higher type has weight w (p ) = (s(p))d /(1 - ) which is the volume of the item divided by (1 - ). We begin by showing that this weighting function is valid for our algorithm. of weight. However, for the case of cubes, we only have M + 1 different types of items. All large items of type i have the same weight. All small items have the same ratio of weight to volume. Therefore the exact contents of a bin are not crucial. In order to define a packed bin, we only Proof. For i M , when a bin is to be closed, there are no need to know how many items there are of each type, and the empty sub-bins of size 1/i. There are at most 2d - 1 empty volume of the small items. To maximize the weight we can sub-bins of each other size by Claim 1. This gives a total assume that the large items are as small as possible (without k k -d unused volume of at most (2d - 1) C = 1/id . changing their type), and the rest of the bin is filled with 1 (2 i) small items. L A I M 3 . The occupied volume in each closed bin of type Formally, we define a pattern as a tuple q = i M is at least 1 - . q1 , . . . , qM -1 , where there exists a feasible packing into a single bin containing qi items of type i for all 1 i M - 1. Proof. A hypercube which was assigned into a sub-bin of This generalizes the definition from [24]. The weight of a k k size 1/(2 i) always has size of at least 1/(2 (i + 1)). pattern q is at most Therefore the ratio of occupied space and existing space in . 1 M -1 d d each used sub-bin is at least i /(i + 1) . When a bin is M -1 i i qi qi 1 d closed, the total volume of used sub-bins is at least 1 - 1/i (2.1) w (q ) = - + id 1- (i + 1)d by Claim 2. Therefore the occupied volume in the bin is =1 =1 d d d d d at least i /(i + 1) (1 - 1/i ) = (i - 1)/(i + 1) . We Note that for any given pattern the amounts of items of types use i M and M d M + 1 to get (id - 1)/(i + 1)d M , . . . , 2M - 1 are unspecified. However, as mentioned M d d d+1 (M N 1)/(M + 1) ( M +1 ) - 1 - . above, the weight of such items is always their volume ow we are ready to analyze the performance. We divided by 1 - . Therefore (2.1) gives an upper bound for define a weighting function for A L G [26]. Each item with the total weight that can be packed in a single bin for a given p type 1 i M - 1 has weight w (p) = 1/id . Each pattern q . Summarizing, we have the following Theorem. Note that the above claims bound the volume of sub-bins that are not used at all. There is some waste of volume also due to the fact that each item does not fill its sub-bin totally. We compute this waste later. T H E O R E M 2 . 1 . The asymptotic performance ratio of A L G is upper bounded by maxq w (q ), where the maximum is taken over all patterns q that are valid for A L G . In order to use the Theorem, we need the following geometric Claim. We immediately formulate it in a general way so that we can also apply it in the next section. C L A I M 4 . Given a packing of hyperboxes into bins, such that each component j is bounded in an interval (1/(kj + 1), 1/kj ], where kj 1 is an integer, then each bin has at d most j =1 kj hyperboxes packed in it. Proof. We prove the claim by induction on the dimension. Clearly for d = 1 the claim holds. To prove the claim for d > 1, the induction hypothesis means that a hyperplane of dimension d - 1 through the bin which is parallel to one of the sides (the side which is the projection of the bin d-1 on the first d - 1 dimensions) can meet at most j =1 kj hyperboxes. Next, take the projection of the hyperboxes and the bin on the last axis. We get short intervals of length in (1/(kd + 1), 1/kd ] (projections of hypercubes) on an main interval of length 1 (the projection of the bin). As mentioned above, each point of the main interval can have the projection d-1 of at most j =1 kj items. Consider the short intervals as an interval graph. The size of the largest clique is at most d-1 j =1 kj . Therefore, as interval graphs are perfect, we can d-1 colour the short intervals using j =1 kj colours. Note that Proof. Each closed bin of type 1 i M - 1 contains id items. All sub-bins are used when the bin is closed, and thus it contains a total weight of 1. Each closed bin of type M i 2M - 1 has occupied volume of at least 1 - by Claim 3, and therefore the weights of the items in such a bin sum up to at least 1. A constant number of bins is active (at most 2M - 1). Thus the total number of bins used by A L G for a given input sequence is upper bounded by the total weigBt of the items plus a constant. h L En M A 2 . 1 . For all input sequences , costALG ( ) M i=1 w (pi ) + O (1). y this Lemma, for any given > 0, the asymptotic performance ratio of our algorithm can be upper bounded by the maximum amount of weight that can be packed in a single bin: for a given input sequence (with fixed weight w), the offline algorithm minimizes the number of bins that it needs to pack all items in by packing as much weight as possible in each bin. If it needs k bins, the performance ratio on this input is w/k , which is also the average weight per offline bin. Therefore we need to find the worst case offline bin, i.e. an offline bin which is packed with a maximum amount 217 L E M M A 2 . 3 . By choosing M correctly, A L G has an asymptotic performance ratio of O (d/ log d). Any bounded E M M A 2 . 2 . Let = lim inf 0 maxq w (q ), where the space algorithm (in particular A L G ) has an asymptotic permaximum is taken over all patterns q that are valid for A L G . formance ratio of (log d). Then the asymptotic performance ratio of any bounded space algorithm is at least . Proof. We first show the upper bound. Take M = 2d/ log d. M The occupied area in bins of small types is at least ( M +1 )d+1 Proof. We show that there is no bounded space algorithm by the proof of Claim 3. This is greater than ( M +1 )-d = M with an asymptotic performance ratio strictly below . (1 + 1/M )-d = (1 + (log d)/(2d))-d , which tends to For any > 0, there exists an (0, ) such that e-(log d)/2 = (elog d )-1/2 = 1/ d for d . R (A L G ) (1 + ). Consider the pattern q for which Suppose the input is I . Denote by Ii the subsequence w (q ) is maximal. We write w (q ) = (1 + ) for some of items of type i (i = 1, . . . , M ), where we consider all [0, ]. the small types as a single type. Then we have A L G (Ii ) = Note that a pattern does not specify the precise sizes O P T (I ) O P T (I ) for i = 1, . . . , M - 1, since if items i of any of the items in it. Based on q , we define a set of only one type arrive, our algorithm packs them perfectly. of hypercubes that can be packed together in a single bin. Moreover, A L G (I ) = O (d)· O P T(I ) = O (d)· O P T(I ) M MM For each item of type i in q , we take a hypercube of size for i = M . Thus A L G(I ) = i=1 A L G (Ii ) (M - 1/(i + 1) + for some small > 0. Take V = 1 - M -1 1)O P T(I ) + O ( d)O P T(I ) = O (d/ log d)O P T(I ). d i=1 qi (1/(i + 1) + ) . We add a large amount of small We now prove the lower bound. Consider the following hypercubes of total volume V , where the sizes of the small lower bound construction. We use log d phases. In phase hypercubes are chosen in such a way that they can all be i, N ((2i - 1)d - (2i - 2)d ) items of size 2-i (1 + ) arrive, packed in a single bin together with the large hypercubes where < 2- log d 1/d. OPT can place all these items prescribed by q . By the definition of a pattern, such a packing in just N bins by using the following packing scheme. Each is feasible for sufficiently small. bin is packed identically, so we just describe the packing of a Define the following input for a bounded space algosingle bin. The first item is placed in a corner of the bin. We rithm. Let N be a large constant. The sequence contains assign coordinates to the bin so that this corner is the origin M phases. The last phase contains a volume N V of small and all positive axes are along edges of the bin. (The size of hypercubes. Phase i (1 i M - 1) contains N qi hythe bin in each dimension is 1.) percubes of size 1/(i + 1) + . After phase i, almost all Consider any coordinate axis. We reserve the space hypercubes of this phase must be packed into closed bins between (1 - 21-i )(1 + ) and (1 - 2-i )(1 + ) for items (except a constant number of active bins). Each such bin of phase i. Note that this is exactly the size of such an may contain up to id items, which implies that in each phase item. By doing this along every axis, we can place all i, N ni /id - O (1) bins are closed. The last phase contributes (2i - 1)d - (2i - 2)d items of phase i. (There would at least V - O (1) extra bins. The cost of the online algorithm M -1 be room for (2i - 1)d items if we used all the space until is i=1 N qi /id + V - O (M ). But the optimal offline cost (1 - 2-i )(1 + ) along each axis; we lose (2i - 2)d items is simply N . Taking = 1/N and letting N grow without because the space until (1 - 21-i )(1 + ) is occupied.) bound, N becomes much larger than M and the asymptotic The minimum number of bins that any bounded space performance ratio of M y bounded space on-line algorithm is online algorithm needs to place the items of phase i is an -1 lower bounded by i=1 qi /id + V0 . Note that the weight of 2i -2 N ((2i - 1)d - (2i - 2)d )/(2i - 1)d = N (1 - ( 2i -1 )d ) items. this set of hypercubes according to our definition of weights M Note that the contribution of each phase i to the total number tends to i=-1 qi /id + V0 /(1 - ) = w (q ) = (1 + ) as 1 of bins required to pack all items is strictly decreasing in M -1 0. Therefore i=1 qi /id + V0 (1 - )(1 + ) i. Consider the contribution of the last phase, which is (1 -T ). phase log d . Since log d 1 + log d, it is greater than 2d N (1 - ( 2d-2 )d ) = N (1 - (1 - 2d1 )d ) N (1 - e-1/2 ) > his Lemma implies that our algorithm is the best 0.39N for -1l d 2. Thus all log-1 terms all contribute at al d possible bounded space algorithm. More precisely, for every least 0.39N , and the total number of bins required is at least > 0, there exists an (0, ) such that R (A L G ) 0.39N ( log d ). This implies a lower bound of (log d) on (1 + ), and no bounded space algorithm has an asymptotic the aFymptotic performance ratio of this problem. s performance ratio below (1 - ). This also implies that our weighting function cannot be improved and determines the inally, we give an overview of the upper and lower asymptotic performance ratio exactly. However, we have no bounds we can show for small dimensions. The upper the number of intervals of each independent set is at most kd (due to length), and so the total number of intervals is at d most j =1 kj . L general formula for this asymptotic performance ratio . We do have the following bounds. 218 Proof. Note that the number of sub-bins of size d (1/s1 , . . . , 1/sd ), is initialized to be i=1 si , and de3 An optimal algorithm for bounded space packing of cays until it reaches the value zero. The cutting process hyperboxes does not create more than a single empty sub-bin of each Next we describe how to extend the algorithm for hypercubes size. This is true for all the sub-bins created except for the to handle hyperboxes instead of hypercubes. This algorithm smallest size that is created in any given process. For that also uses the parameter . The value of M as a function of size we create two identical sub-bins. However, one of them is picked so that M 1/(1 - (1 - )1/(d+2) ) - 1. Similarly is filled right away. to the previous algorithm, the hyperboxes are classified into Furthermore, no sub-bins of existing sizes are created types. A arriving hyperbox b of dimensions (b1 , b2 , . . . , bd ), due to the choice of the initial sub-bin. The initial sub-bin is is classified as one of (2M - 1)d types depending on its chosen to be of minimum volume among the ones that can components: a type of a hyperbox is the vector of the types contain the item, and hence all the created sub-bins (all of of its components. which can contain the item) are of smaller volume than any There are 2M - 1 types of components. A component other existing sub-bin that can contain the item. C larger than 1/M has type i if 1/(i + 1) < bi 1/i, and is called large. A component smaller than 1/M has L A I M 6 . The occupied volume in each closed bin of type type i, where M i 2M - 1, if there exists a non- (s1 , . . . , sd ) is at least negative integer fi such that 1/(i + 1) < 2fi bi 1/i. Such i components are called small. (1 - ) si /(si + 1), Each of the (2M - 1)d types is packed separately and L independently of the other types. The algorithm keeps one active bin for each type (s1 , . . . , sd ). When such a where L is the set of large components in this type. d bin is opened, it is split into i=1 si identical sub-bins of Proof. To bound the occupied volume in closed bins, note dimensions (1/s1 , . . . , 1/sd ). On arrival of a hyperbox p, that a sub-bin which was assigned an item is full by a fraction after classification into a type, a sub-bin has to be found of at least for it. If there is no sub-bin in the current bin that is larger d-|L| i M id than p in every dimension, we close the bin and open a new si si . one. Otherwise, we take an empty sub-bin that has minimum si + 1 M +1 si + 1 =1 L volume among all sub-bins that can contain p. Now consider the components of p one by one. If the Considering sub-bins that were empty when the bin was i-th component is large, the sub-bin has the correct size in closed, by Claim 5 there may be one empty sub-bin of each this dimension: its size is 1/si whereas the component is in size (1/(2f1 s1 ), . . . , (1/(2fd sd )), with the restrictions that (1/(si - 1), 1/si ]. fi is a nonnegative integer for i = 1, . . . , d, fi = 0 for each If the i-th component is small, the size of the sub-bin large component i, and there exists some i {1, . . . , d} such in the i-th dimension may be too large. Suppose its size that fi = 0. s is 1/(2f i ) whereas the hyperbox has size 1/(2f si ) in this If there are no small components, there can be no empty dimension for some f > f . In this case, we divide the sub-bins because large components never cause splits into sub-bin into two equal parts by cutting halfway (across the sub-bins, so all sub-bins are used when the bin is closed. i i-th dimension). If the new sub-bins have the proper size, This gives a bound of L si /(si + 1). take one of the two smallest sub-bins that were created, and If there is only one small component, the total volume continue with the next component. Otherwise, take one of of all empty sub-bins that can exist is 1/(s1 . . . sd ) · ( 1 + 1 + 2 4 bounds were found by formulating a linear program and solving it (using Matlab). The lower bounds were found by constructing bins with high weights. We omit the details of these constructions. All results for d > 1 improve upon existing results. d Lower bound Upper bound 1 1.69103 1.69103 2.35656 2.3722 2 3 2.94457 3.0672 3.36547 3.7595 4 5 3.74913 4.4052 4.04789 5.0126 6 7 4.27726 5.7084 the new sub-bins and cut it in half again, repeating until the size of a created sub-bin is 1/(2f si ). Thus we ensure that the sub-bin that we use to pack the item p has the proper size in every dimension. We then place this item anywhere inside the sub-bin. We now generalize the proofs from the previous section for this algorithm. C L A I M 5 . Consider a type (s1 , . . . , sd ), and its active bin. For every vector (f1 , . . . , fd ) = 0 of nonnegative integers such that fi = 0 for each large component i, there is at most one empty sub-bin of size (1/(2f1 s1 ), . . . , 1/(2fd sd )). 219 . . .) 1/(s1 . . . sd ) 1/M , since one of the components is small (type is at least M ) and all other components have type at li ast 1. The occupied volume is at least (1 - 1/M ) · e i M M d+2 L (si /(si + 1)) ( M +1 ) L (si /(si + 1)). M +1 This holds for any d 2 and M 2. If there are r 2 small components, the total volume of empty sub-bins is at most (2r - 1)/(s1 s2 . . . sd ) (2r - 1)/M r 2r /M r . (We get the factor 2r - 1 by enumerating over all possible choices of the values fi .) We get that each bin is full by at least a fraction of 1 M ri 2r si -r M M +1 si + 1 L r+2 i M M r - 2r i si si = (M + 1)r si + 1 M +1 si + 1 L L d+2 i M si . M +1 si + 1 L have w (p ) v (p ) = = d i i 1 1i i bi b 1- si =1 L L / i 1 1i 1 si + 1 > . 1- si bi 1- si + M 2 L L As tends to zero, this bound approaches the inverse of the number in Claim 6. This means that the total weight of items in a closed bin is no smaller than 1. J ust like in Section 2, this Lemma implies that the asymptotic worst case ratio is upper bounded by the maximum amount of weight that can be packed in a single bin. We now prove a technical Lemma that implies that this weighting function is also "optimal" in that it determines the true asymptotic performance ratio of our algorithm. D E FI N I T I O N 1 . The pseudo-volume of a hyperbox H = i (b1 , . . . , bd ) is defined as L bi , where L is the set of large / components of H . The penultimate inequality holds for M r - 2r M r+2 /(M + 1)2 , which holds for any r 2 and M 4. M Using ( M +1 )d+2 1 - we get the Claim. W Suppose that for a given set of hyperboxes X , we can partition the dimensions into two sets, A and B , such that e now define a weighting function for our algorithm. The weight of a hyperbox p with components (b1 , . . . , bd ) for each dimension i in A, we have that the i-th components of all hyperboxes in X are bounded in an interval (1/(kj + and type (s1 , . . . , sd ) is defined as 1), 1/kj ]. There are no restrictions on the dimensions in B . i 1i 1 (Thus such a partition can always be found by taking A = .) w (p) = , bi For a hyperbox H X , define the generalized pseudo1- si i L L / volume of the components in B by v (H, B ) = B bi , where bi is the i-th component of H . Define the total where L is the set of large components in this type. generalized pseudo-volume of all hyperboxes in a set X by H M L En M A 3 . 1 . For all input sequences , costalg ( ) v (X, B ) = X v (H , B ). i=1 w (pi ) + O (1). C L A I M 7 . For a given set X of hyperboxes, for sufficiently Proof. In order to prove the claim, it is sufficient to show that large N , any packing of X into bins requires at least each closed bin contains items of total weight of at least 1. v (X, B )(1 - 1 )|B | / i ki bins, where A and B form a A N Consider a bin filled with hyperboxes with type (s1 , . . . , sd ). partitioning of the dimensions as described above. It is sufficient to consider the subsequence of the input that contains only items of this type, since all types are packed Proof. We prove the claim by induction on the number of independently. We build an input for which both the dimensions in B . For |B | = 0, we find that the total behavior of the algorithm and the weights are the same as generalized pseudo-volume of X is simply the number of for , and show the claim holds for . Let < 1/M 3 be a hyperboxes in X (since the empty product is 1) and thus the very small constant. claim is true using Claim 4. For a hyperbox p with components (b1 , . . . , bd ) and Assume the claim is true for |B | = 0, . . . , r -1. Suppose type (s1 , . . . , sd ), let p = (b1 , . . . , bd ) be defined as |A| = d - r < d. Take any dimension i B . We replace follows. For i L, bi = bi . For i L, bi = 1/(si + 1) + < each hyperbox H , with component bi in dimension i, by / 1 1/si . As p and p have the same type, they require a sub-bin N bi hyperboxes that have N as their i-th component, and of the same size in all dimensions. Therefore the algorithm are identical to H in all other components. Here N is taken 1 packs in the same way as it packs . Moreover, according sufficiently large, such that N < bi . Clearly, the new input h i to the definition of weight above, p and p ave the same X s no harder to pack, as we split each item into parts weight. whose sum is smaller than or equal to the original items. Let v (p) denote the volume of an item p. For p , we The total generalized pseudo-volume of the hypercubes in 1 compute the ratio of weight and volume of the item p . We X is at most a factor of 1 - N smaller than that of X . 220 4 An unbounded space algorithm for square packing We define a two-dimensional version of Modified Harmonic that we call MH2 . It uses seven item types (intervals in j 1 (0, 1]), denoted by 1, 1a, 2, 2a, 3, 4, 5 in order of decreasing v (X , B ) · (1 - )r-1 / kj N size. The algorithm uses a variable (1/3, 0.385). The A{i} upper bound for type i (i = 1, . . . , 5) is 1/i. The upper bins to pack the modified ijnput X . Using that ki = N , this bound for type 1a is 1 - , and for 2a it is . 1 is v (L , B ) · (1 - N )r / A kj bins. X MH2 packs all items of size at most 1/5 (type 5) using the algorithm from Section 2 for small items. That is, we 1 etting = 1 - (1 - N )d , we get that the required divide the items into 5 subtypes, and for each item of subtype j number is at least v (X, B )(1 - )/ A kj bins, where i we call the function A S S I G N L A R G E (i) (we take M = 5). 0 as N . In the remainder, we will take A to be the Items of type 2a are partially put three to a bin, in such dimensions where the components of the hyperboxes in X a way that a type 1a item could be put in the same bin with are large, and B the dimensions where they are small. Note them, and partially put four to a bin, in the four corners. that this choice of A satisfies the constraints on A above, These items are colored red and blue, respectively. We use and that this reduces the generalized pseudo-volume to the a second parameter (1/5, 1/4) to denote the fraction of (normal) pseudo-volume defined before. We are ready to type 2a items that are colored red. The values of and prove the following Lemma. will be chosen in such a way that the asymptotic performance ratio of MH2 is minimized. We will find 0.2094 and L E M M A 3 . 2 . Let > 0. Suppose the maximum amount 0.3803. of weight that can be packed in a single bin is . Then Items of types 1, 2, 3, and 4 are packed in bins that only our algorithm has an asymptotic performance ratio of , contain items of one type. Full bins contain 1, 4, 9, and and the asymptotic performance ratio of any bounded space 16 items, respectively. By the proof of Claim 3, full bins algorithm is at least (1 - ) . containing items of type 5 have occupied area of at least (M d - 1)/(M + 1)d = 24/36 = 2/3. Proof. The first statement follows from Lemma 3.1. We We give an overview of the types, weights and expanshow a lower bound of value which tends to on the sions in Table 1. asymptotic performance ratio of any bounded space algorithm. Consider a packed bin for which the sum of weights is Table 1: Item weights and expansions for MH2 d . Partition the hyperboxes of this bin into M types in the following way. Each component is either of a type in b Type Max. size W1 W2 E1 E2 {1, . . . , M - 1} or small (i.e. of a type i, i M ). Let N 1 1 1 1 1 1 e a large constant. The sequence consists of phases. Each (1-)2 (1-)2 t 1- 1 0 4 0 1a phase consists of one item from the packed bin, repeated N 2 1/2 1/4 1/4 1/(42 ) 1/(42 ) imes. The optimal offline cost is therefore N . Using Claim 1- 3+ 9-9 9+3 2a 7 we see that the amount of bins needed to pack a phase 4 12 4 4 t 3 1/3 1/9 1/9 16/9 16/9 which consists of an item p repeated N imes is simply 4 1/4 1/16 1/16 25/16 25/16 N w(p)(1 - )(1 - ). Therefore the cost of an on-line 3 3 5 1/5 x x 3/2 3/2 algorithm is at least N (1 - )(1 - ) - O (1), which 2 2 makes the asymptotic performance ratio arbitrarily close to (1 - ) . . We omit the proof of the following Theorem. Furthermore, we can determine the asymptotic performance ratio of our algorithm for hyperbox packing. Com- T H E O R E M 4 . 1 . Denote by wi the maximum amount of paring to the unbounded space algorithm from [10] we can weight that can be packed into a single bin according to measee that all the weights we defined are smaller than or equal sure Wi (i = 1, 2). Then the asymptotic performance ratio to the weights used in [10]. So the asymptotic performance of MH2 is upper bounded by max(w1 , w2 ). ratio is not higher. However, it can also not be lower due to the general lower bound for bounded space algorithms. This The expansion of type 5 items (small items) is 3/2. To means that both algorithms have the same asymptotic per- simplify the calculations, we will assume that it is instead formance ratio, namely ( )d , where 1.691 is the 25/16. This can only make the asymptotic performance asymptotic performance ratio of the algorithm H A R M O N I C ratio worse, so we will calculate an upper bound for the [20]. asymptotic performance ratio. Using this value enables us So if we write B = B \{i}, we have v (X , B 1 v (X, B )(1 - N ). By induction, it takes at least ) · 1 N 221 to ignore the items of type 4, since they also have expansion 25/16: we will assume that after taking some items from types 1, 1a, 2, 2a, and 3 we can fill up the rest of the bin entirely with items of expansion 25/16 (this is the worst case). To find a bin with maximal weight, we need to try all possible combinations of items of types 1, 1a, 2, 2a, and 3 and fill up the rest with "sand" (small items). The weight is maximized by minimizing the size of all the large items that we use (since the weight they contribute does not depend on their size, and it maximizes the area available for other large 25 items and for small items). We take = 36 (92 - 1). This choice of ensures that if we have a bin with a type 2 item (of minimal size), and we replace it with a type 2a item (of minimal size) and fill the remaining area with sand, the total weight is unchanged: we have 1/4 = 1- + 25 (2 - 1/9). 4 16 We use the following Lemma from [25]. This Lemma can also be proved using Claim 4. L E M M A 4 . 1 . If a square of size strictly greater than 1/2 is packed in the unit square then at most 5 squares of size strictly greater than 1/4 can be packed with it. T H E O R E M 4 . 2 . MH2 maintains a asymptotic performance ratio of at most 2.270876. 25 The total weight is at most 1 + 3/4 + /4 + 2/9 + 16 (1 - 2 (1 - ) - 1/3 - 1/8). Case 3. Now suppose there is an item of type 1a. Then the weight of the bin is maximal if we use W1 (using W2 , the total weight is now lower than in Case 1). There are at most 5 items of type 2, 2a, or 3. By the remarks above Lemma 4, we do not need to distinguish between bins that only differ in that one of them has a type 2 item where the other has a type 2a item and more sand. Since type 2 and 2a items have higher weight than items of type 3 (because < 0.385), we take 3 of them, and 2 of type 3 (here we ignore that items of type 3 do not necessarily fit in a bin that already contains one item of size greater than 1/2 and three items of size greater than , just like in Case 2). 25 The total weight is at most 1 + 3/4 + 2/9 + 16 (1 - 1/4 - 2 3 - 2/16). We take to be the solution of 272 + 18 - 43/4 = 0 that is in the interval (1/3, 0.385). Then the weights in Cases 2 and 3 above are the same, and they are 2.270876. This is an upper bound for the asymptotic performance ratio of MH2 . 5 A 16/11 approximation for offline square packing We present an approximation algorithm for the packing of squares in two-dimensional bins. Proof. We look for a bin with maximal weight. The basic idea is as follows: we classify items as either Case 1. First of all, suppose that there is no item of type small or large. Large items are further classified according to 1 or 1a in the bin. For the remaining items, W1 (p) W2 (p) for all items p. Thus we only need to consider W2 . The type their size. For the large items, we create an optimal solution with the highest expansion is type 2a, which fits at most four using packing patterns derived from an integer program. times in a bin. All other types have expansion at most 16/9 Small items are then packed first into bins with certain large by our choice of , so the total weight of the bin in this case items, and then, if necessary, into bins by themselves. We pack small items only into bins that contain a single is at most (3 + )/3 + (1 - 4/9)16/9 < 2.1. large item of size at least 1/2, and into bins that contain Suppose there is an item of type 1 or 1a. By Lemma 4, at exactly four items (in such bins, the smallest two items have most 5 items of type 2, 2a, or 3 can be packed with them. As total size at least 2/3). In this way, we ensure that such usual we assume that the rest of the bin is filled with items bins (if any exist) contain an amount of items of total area of expansion 25/16. Since the items of type 2, 2a and 3 have nearly 1, i.e. little space is wasted (unused) in such bins. expansion greater than 25/16, the weight is maximized by The key to bounding the approximation ratio is to show that the remaining bins cannot hold too many small items in the taking 5 of them. Case 2. Suppose there is an item of type 1. Then there optimal offline solution. Let A be a set of item sizes. A pattern over A is finite is no item of type 1a; for all other items, W2 (p) W1 (p), so we only need to consider W2 (p). In this case items of type multiset P of squares with sizes in A that fit (in some way) 2 do not fit in the bin. If we place i items of type 2a in the into a unit square. For a pattern P , for 1 j m, define Pj bin, this leaves room for at most 5 - i items of type 3. We to be the number of items of size aj in P . A pattern of order j assume that 5 - i such items can always be placed. (This is is dominant if when we increase the number of items of size a worst-case assumption.) Since the weight of type 2a items aj , the resulting multi-set of items no longer fits in i a unit Pi a 2 . i is higher than that of type 3 items, and the total number of square. The waste of pattern P is defined to be 1 - The following Lemma extends the corresponding type 2a items and type 3 items is assumed to be independent of the number of type 2a items, we maximize the number Lemma from [25]. It is key to proving the approximation of type 2a items. However, at most 4 items of size strictly ratio of 16/11. The proof is omitted. greater than 1/3 fit in one bin, so at most 3 items of type 2a can be placed in this bin together with the item of type 1. L E M M A 5 . 1 . The waste of any dominant pattern which contains at least five items is at most 5/11 0.4545. This leaves two items of type 3. 222 6 Conclusions An open question left by this paper is what the asymptotic performance ratio of the bounded space hypercube packing problem is. We can show that it is (log d), and we conjecture that it is (log d). It should be possible to improve upon the algorithm in section 4. However, at the moment we lack a good way of enumerating all (dominant) patterns in a two-dimensional bin if there are many item types. This is an interesting open problem. References [1] Nikhil Bansal and Maxim Sviridenko. New approximability and inapproximability results for 2-dimensional packing. These proceedings. ´ [2] David Blitz, Andre van Vliet, and Gerhard J. Woeginger. Lower bounds on the asymptotic worst-case ratio of online bin packing algorithms. Unpublished manuscript, 1996. [3] Donna J. Brown. A lower bound for on-line one-dimensional bin packing algorithms. Technical Report R-864, Coordinated Sci. Lab., Urbana, Illinois, 1979. [4] Alberto Caprara. Packing 2-dimensional bins in harmony. In Proc. 43th IEEE Symp. on Found. of Comp. Science, pages 490­499, 2002. [5] Fan R. K. Chung, Michael R. Garey, and David S. Johnson. On packing two-dimensional bins. SIAM Journal on Algebraic and Discrete Methods, 3:66­76, 1982. [6] Edward G. Coffman, Michael R. Garey, and David S. Johnson. Approximation algorithms for bin packing: a survey. In D. Hochbaum, editor, Approximation algorithms. PWS Publishing Company, 1997. [7] Don Coppersmith and Prabhakar Raghavan. Multidimensional online bin packing: Algorithms and worst case analysis. Operations Research Letters, 8:17­20, 1989. [8] Jose Correa and Claire Kenyon. Approximation schemes for multidimensional packing. These proceedings. ´ [9] Janos Csirik, Johannes B. G. Frenk, and Martine Labbe. Two dimensional rectangle packing: on line methods and results. Discrete Applied Mathematics, 45:197­204, 1993. ´ ´ [10] Janos Csirik and Andre van Vliet. An on-line algorithm for multidimensional bin packing. Operations Research Letters, 13(3):149­158, Apr 1993. ´ [11] Janos Csirik and Gerhard J. Woeginger. On-line packing and covering problems. In A. Fiat and G. J. Woeginger, editors, Online Algorithms: The State of the Art, volume 1442 of Lecture Notes in Computer Science, pages 147­177. Springer-Verlag, 1998. [12] Wenceslas Fernandez de la Vega and George S. Lueker. Bin packing can be solved within 1 + in linear time. Combinatorica, 1:349­355, 1981. [13] Carlos E. Ferreira, Flavio K. Miyazawa, and Yoshiko Wakabayashi. Packing squares into squares. Pesquisa Operacional, 19(2):223­237, 1999. [14] Gabor Galambos. A 1.6 lower bound for the two-dimensional online rectangle bin packing. Acta Cybernetica, 10:21­24, 1991. ´ [15] Gabor Galambos and Andre van Vliet. Lower bounds for 1-, 2-, and 3-dimensional online bin packing algorithms. Computing, 52:281­297, 1994. [16] Michael R. Garey, Ronald L. Graham, and Jeffrey D. Ullman. Worst-case analysis of memory allocation algorithms. In Proceedings of the Fourth Annual ACM Symposium on Theory of Computing, pages 143­150. ACM, 1972. [17] David S. Johnson. Fast algorithms for bin packing. Journal Computer Systems Science, 8:272­314, 1974. [18] Narendra Karmarkar and Richard M. Karp. An efficient approximation scheme for the one-dimensional bin-packing problem. In Proceedings of the 23rd Annual Symposium on Foundations of Computer Science, pages 312­320, 1982. [19] Yoshiharu Kohayakawa, Flavio K. Miyazawa, Prabhakar Raghavan, and Yoshiko Wakabayashi. Multidimensional cube packing. In Jayme Szwarcfiter and Siang Song, editors, Electronic Notes in Discrete Mathematics, volume 7. Elsevier Science Publishers, 2001. [20] C. C. Lee and D. T. Lee. A simple online bin packing algorithm. Journal of the ACM, 32:562­572, 1985. [21] K. Li and K. H. Cheng. A generalized harmonic algorithm for on-line multi-dimensional bin packing. manuscript, 1990. [22] Frank M. Liang. A lower bound for online bin packing. Information Processing Letters, 10:76­79, 1980. [23] Flavio K. Miyazawa and Yoshiko Wakabayashi. Cube packing. Theoretical Computer Science, 297(1-3):355­366, 2003. [24] Steve S. Seiden. On the online bin packing problem. Journal of the ACM, 49(5):640­671, 2002. [25] Steve S. Seiden and Rob van Stee. New bounds for multidimensional packing. Algorithmica, 36(3):261­293, 2003. [26] Jeffrey D. Ullman. The performance of a memory allocation algorithm. Technical Report 100, Princeton University, Princeton, NJ, 1971. ´ [27] Andre van Vliet. An improved lower bound for online bin packing algorithms. Information Processing Letters, 43:277­ 284, 1992. ´ [28] Andre van Vliet. Lower and upper bounds for online bin packing and scheduling heuristics. PhD thesis, Erasmus University, Rotterdam, The Netherlands, 1995. ´ [29] Andre van Vliet. On the asymptotic worst case behaviour of harmonic fit. Journal of Algorithms, 20:113­136, 1996. [30] Gerhard J. Woeginger. Improved space for bounded-space online bin packing. SIAM Journal on Discrete Mathematics, 6:575­581, 1993. [31] Andrew C. C. Yao. New algorithms for bin packing. Journal of the ACM, 27:207­227, 1980. 223