Improved Approximation Algorithms for Three-Dimensional Bin Packing
Abstract
We study three fundamental three-dimensional (3D) geometric packing problems: 3D (Geometric) Bin Packing (3d-bp), 3D Strip Packing (3d-sp), and Minimum Volume Bounding Box (3d-mvbb), where given a set of 3D (rectangular) cuboids, the goal is to find an axis-aligned nonoverlapping packing of all cuboids. In 3d-bp, we need to pack the given cuboids into the minimum number of unit cube bins. In 3d-sp, we need to pack them into a 3D cuboid with a unit square base and minimum height. Finally, in 3d-mvbb, the goal is to pack into a cuboid box of minimum volume.
It is NP-hard to even decide whether a set of rectangles can be packed into a unit square bin – giving an (absolute) approximation hardness of 2 for 3d-bp and 3d-sp. The previous best (absolute) approximation for all three problems is by Li and Cheng (SICOMP, 1990), who gave algorithms with approximation ratios of 13, , and , respectively, for 3d-bp, 3d-sp, and 3d-mvbb. We provide improved approximation ratios of 6, 6, and , respectively, for the three problems, for any constant .
For 3d-bp, in the asymptotic regime, Bansal, Correa, Kenyon, and Sviridenko (Math. Oper. Res., 2006) showed that there is no asymptotic polynomial-time approximation scheme (APTAS) even when all items have the same height. Caprara (Math. Oper. Res., 2008) gave an asymptotic approximation ratio of , where is the well-known Harmonic constant in Bin Packing. We provide an algorithm with an improved asymptotic approximation ratio of . Further, we show that unlike 3d-bp (and 3d-sp), 3d-mvbb admits an APTAS.
Keywords and phrases:
Approximation Algorithms, Geometric Packing, Multidimensional PackingCategory:
Track A: Algorithms, Complexity and GamesFunding:
Debajyoti Kar: Google PhD Fellowship.Copyright and License:
![[Uncaptioned image]](x1.png)
2012 ACM Subject Classification:
Theory of computation Packing and covering problemsEditors:
Keren Censor-Hillel, Fabrizio Grandoni, Joël Ouaknine, and Gabriele PuppisSeries and Publisher:

1 Introduction
Three-dimensional (3D) packing problems are used to model several practical settings in production and transportation planning – ranging from cargo management, manufacturing, 3D printing and prototyping, to cutting and loading applications. In the 1960s, Gilmore and Gomory [27] introduced 3D packing in the context of the cutting stock problem in operations research, where given a stock material (3D cuboid), the goal is to cut out a set of required items (smaller 3D cuboids) by a sequence of end-to-end cuts. Around the same time, Meir and Moser [50] asked a combinatorial question: given a set of cubes, when can we pack them in a given cuboid? Since then, due to its inherent mathematical aesthetics, computational nature, and practical relevance, the study of 3D packing has led to the development of several techniques in mathematics, computer science, and operations research.
In this paper, we consider three classical 3D packing problems. In all of these problems, the input is a collection of (rectangular) cuboids (items), each specified by their height, width, and depth. In the 3D Bin Packing (3d-bp) problem, the goal is to output a packing of all the items using the minimum number of bins, where each bin is a unit cube. In the 3D Strip Packing (3d-sp) problem, we are given a three-dimensional strip having a square base and unbounded height, and we have to pack all items minimizing the height of the strip. Finally, in the Minimum Volume Bounding Box (3d-mvbb) problem, we seek to obtain a cuboidal box of minimum volume that can accommodate all input items. In all these problems, the items cannot be rotated about any axis, and they must be packed non-overlappingly. Further, we assume that all items and bins/boxes are axis-aligned.
With the recent exponential growth in transportation and shipping, specially with the advent of e-commerce and UAVs, these problems are receiving increasingly more attention. For instance, in container ship loading, it is crucial to optimize the placement of cargo to maximize space usage while minimizing the number of containers needed. In pallet loading, manufacturers strive to stack goods on pallets in a way that maximizes storage capacity and ensures secure transport. Further, in supply chain management, it is crucial to optimize the arrangement of goods in storage to fit within the smallest possible space, reducing storage costs and enhancing inventory accessibility. The survey by Ali, Ramos, Carravilla, and Oliveira [3] provides a comprehensive overview of 3D packing, with more than two hundred research articles. We refer readers to [22, 32, 45, 17, 53, 16, 38, 44, 48, 47] and [26, 11, 4, 20, 56, 55] for important empirical procedures and heuristics to 3d-bp and 3d-sp, respectively. There are also many practical programming competitions for these problems, e.g., OPTIL 3D Bin Packing Challenge [2] and ICRA VMAC Palletization Competition [1].
In contrast to the above, the theoretical exploration of 3D packing has been significantly limited due to its inherently complicated nature. All three considered problems are NP-hard. In fact, 3d-bp and 3d-sp generalize several classical strongly NP-hard problems in scheduling and packing, including (1D) bin packing, multiprocessor scheduling [43], packing squares into squares [23], and packing cubes into cubes [46]. In this paper, we study the absolute and asymptotic approximation algorithms for these problems. Given an algorithm for a minimization problem , the absolute approximation ratio of is defined as , where is the set of all input instances for , and are the values of the solution provided by and the optimal solution for an input instance , respectively. The asymptotic approximation ratio (AAR) is defined as: A problem is said to admit an asymptotic polynomial-time approximation scheme (APTAS) if, for any , there exists a polynomial-time algorithm with AAR of . 3d-bp and 3d-sp generalize 2D Bin Packing. Thus they do not admit an APTAS, as 2D Bin Packing has an asymptotic approximation hardness of [13]. Furthermore, even for squares, it is NP-hard to decide if a set of squares can be packed in a single square bin or not [23] – thus giving an absolute approximation hardness of 2 for 3d-bp and 3d-sp.
Two-dimensional variants of these problems have been extensively studied. For 2d-bp, Harren, Jansen, Prädel, Schwarz, and van Stee [30] gave a tight absolute 2-approximation, and a line of work [12, 7, 35] culminated in an asymptotic 1.406-approximation due to Bansal and Khan [10]. For 2d-sp, the asymptotic approximation regime is settled by the AFPTAS due to Kenyon and Rémila [40]. However, the best-known absolute approximation ratio for 2d-sp stands at [29] and there is a -hardness. In pseudopolynomial-time, there is an almost tight (absolute) -approximation algorithm [36, 31]. Finally, for 2d-mvbb, Bansal, Correa, Kenyon, and Sviridenko [8] gave a PTAS.
For 3d-bp, Csirik and van Vliet [18] gave an asymptotic approximation ratio of , where is the omnipresent Harmonic constant [41] in Bin Packing, and the same ratio was achieved by Epstein and van Stee [21] by an online algorithm using bounded space. This was later improved to by Caprara [12], which stands as the currently best-known asymptotic approximation ratio for 3d-bp.
For 3d-sp, Li and Cheng [43] demonstrated that simple heuristics such as NFDH or FFDH for 2D packing [15] have unbounded AARs. Then they provided an algorithm that returns a packing into a strip of height at most , where denotes the optimal Strip Packing height, and is the maximum height of an input item. Afterwards, there has been a long line of work [43, 42, 52, 51, 37, 9] on the asymptotic approximability of 3d-sp, culminating in a -approximation by Jansen and Prädel [34]. However, all these improved asymptotic approximation algorithms incur huge additive loss (more than 100).
The authors in [19] obtained an absolute approximation ratio of for 3d-sp, and claimed it to be the best-known ratio for the problem. However, Li and Cheng [43] had also designed an algorithm that returns a packing into a strip of height at most . This already gives a better absolute approximation ratio of for 3d-sp. Since is a lower bound on the minimum number of unit (cube) bins needed to pack all items, an absolute -approximation for 3d-sp directly implies an absolute -approximation for 3d-bp – one can obtain bins by cutting a 3d-sp solution at integral heights, followed by packing the items intersected by the cutting planes into additional separate bins. Thus the -approximation for 3d-sp implies an absolute 13-approximation for 3d-bp, which we believe to be the best-known approximation ratio for 3d-bp.
Finally, it is easy to obtain an absolute -approximation for 3d-mvbb from an absolute -approximation for 3d-sp. Applying this strategy to the claimed -approximation algorithm for 3d-sp [19], Alt and Scharf [6] obtained a -absolute approximation for 3d-mvbb. However, as mentioned before, the result of Li and Cheng [43] can also be extended to a -approximation for 3d-mvbb.
There have been some improvements for special cases. For example, Bansal, Correa, Kenyon, and Sviridenko [8] provided an APTAS for -dimensional bin packing with -dimensional cubes. Harren [28] gave APTAS for -dimensional strip packing with -dimensional cubes when the base of the strip has a bounded aspect ratio. Jansen, Khan, Lira, and Sreenivas [33] extended the APTAS to more general bases (not necessarily rectangular).
However, for general cuboids, there has been no progress on the absolute approximation ratios for any of the three problems since 1990 [43] and for asymptotic approximation ratio of 3d-bp since 2008 [12]. In [8], the authors mention the inherent difficulty in extending results from 2D packing to 3D packing, due to the more complicated nature of interactions between different types of items in three dimension. In fact, improved approximability of -dimensional geometric Bin Packing and Strip Packing, for , was listed as one of the ten major open problems in the survey on multidimensional packing [14].
1.1 Our contribution
We present improved absolute approximation algorithms for 3d-bp, 3d-sp, and 3d-mvbb. Further, we obtain improved asymptotic approximation algorithms for 3d-bp and 3d-mvbb. Our results are summarized in Table 1.
Problem | Absolute Approximation Ratio | Asymptotic Approximation Ratio | ||
---|---|---|---|---|
Previous Best | Our Result | Previous Best | Our Result | |
3d-bp | 13 [43] | 6 (WR: 5) | [12] | |
3d-sp | [43] | [34] | – | |
3d-mvbb | [43, 6] | [43, 6] |
First, we discuss our results on the absolute approximation algorithms. We show how a packing in bins can be transformed into structured bins; following which, for constant , it is possible to find such a structured packing efficiently using a variant of the Generalized Assignment Problem – giving us an absolute approximation ratio of 6. One interesting idea is that we use an asymptotic approximation algorithm to obtain improved absolute approximation. One of our key ingredients is the asymptotic approximation algorithm for 3d-sp by Jansen and Prädel [37], which provides a packing into height at most . 111The notation means that the implicit constant hidden in big- notation can depend on . Thus, for a sufficiently small appropriate constant , if , then we can actually pack all items into bins, assuming there exists a packing into bins. So, we partition the items into four classes: (large items: all dimensions are greater than ), (width, depth, height less than , resp.). If an item belongs to multiple classes, we assign them to any one arbitrarily. Now large items can be packed in bins by brute-force enumeration in polynomial-time (for constant ). Each of the remaining three classes can be packed into bins. In total, we get bins.
To improve further, we pack large items together with some items from one of the three classes. First, we observe that one of these classes has volume less than . W.l.o.g. let us assume it to be . Now first we use a volume-based argument and use an algorithm from [43] to show that we can pack all items in whose width or depth is less than 1/2. The remaining items in have both width and depth exceeding 1/2. Next, we show that we can guess the packing of large items and almost all items in , except a set of items with small volume. However, with a refined and technical analysis, we finally show that even these remaining items can be packed in the free regions of the six bins. For 3d-bp, this yields an improvement over the previous bound of 13 [43].
Theorem 1.
There exists a polynomial-time 6-approximation algorithm for 3d-bp.
This directly implies an absolute -approximation for 3d-sp – guess the optimal Strip Packing height within a -factor, then use appropriate scaling to apply the above 3d-bp result, and finally stack the obtained six bins. With a more careful analysis, we can show there is some extra empty space in the strip and the resulting height is strictly below 6.
Theorem 2.
There exists a small absolute constant , such that for any , there is a polynomial-time -approximation algorithm for 3d-sp.
When the items can be rotated by around any axis, the approximation ratio for 3d-bp improves to 5 with a more careful analysis.
Theorem 3.
There exists a polynomial-time 5-approximation for 3d-bp with rotations.
Another implication of our result is a -approximation for the 3d-mvbb problem, using the connection between 3d-sp and 3d-mvbb [6]. However, we then use the power of resource augmentation in 2d-bp to obtain an APTAS for 3d-sp when we are allowed to use resource augmentation. With additional technical adaptations, we obtain a -approximation for 3d-mvbb.
Furthermore, surprisingly, unlike 3d-bp and 3d-sp, we show that 3d-mvbb admits an APTAS – settling the asymptotic approximability for the problem.
Theorem 4.
For any , there exists a polynomial-time -approximation algorithm and an asymptotic polynomial-time approximation scheme for 3d-mvbb.
Finally, we turn our attention to the asymptotic approximability of 3d-bp. Towards this, we exploit connections between 3d-sp and 3d-bp. Let be the values of the optimal solution for Strip Packing and Bin Packing, for input , respectively. Then , as the bins can be stacked on top of each other to provide a feasible solution for Strip Packing. Thus, one can trivially obtain a -approximation algorithm as follows. First, we obtain a packing in height using [34]. We then can cut the strip into unit cube bins by cutting it at integral heights. All items that are completely contained within heights are packed in the -th bin. Remaining items that are cut by the - axis-aligned plane at height (these items form one layer of items where each item has height at most ) are packed in -th bin. This would give us a packing into bins.
To improve beyond , our approach will be to find a packing such that the items that are cut do not have large heights. Towards this, we use harmonic rounding [41], where the function rounds up to nearest larger number of the form where . Thus, for , , for . Otherwise, . It is well-known [9] that, for any sequence , with and , for a small enough , we have .
We first round the item heights in using to obtain a new set of items and obtain a 3D Strip Packing of them using the algorithm by [37]. Let be the optimal number of -sized bins needed to pack all items in . Then, it is easy to see that . 222For simplicity, we are ignoring the in the following discussion in this section. Then we have . The last inequality follows from harmonic rounding.
Now we need to ensure that the tall items in packed in the strip with height are not cut by the cutting planes at integral heights – we call this tall-not-sliced property. A similar idea was used by Bansal, Han, Iwama, Sviridenko, and Zhang [9] to obtain an alternate -approximation for 2d-bp. However, 3D packing is much more involved. For this, we exploit the structural properties from the packing by [34]. First, we show that the strip can be divided into cuboids such that, for each cuboid, the corresponding items packed inside are similar. Next, we show that we can pack almost all tall items in of the same height ( for some ) at heights that are multiple of and incur only a small additive loss. This will ensure that none of these items are cut by planes at integral heights. For items with big width and depth, we use a linear program to assign items to the containers. For other items (except a small volume of them), the packing is based on variants of the Next-Fit-Decreasing-Height (NFDH) algorithm [15]. Finally, we show that we can pack the remaining items in the remaining free regions and an additional bins. This provides an improved guarantee for 3d-bp after nearly two decades.
Theorem 5.
For any , there exists a polynomial-time algorithm for 3d-bp with an asymptotic approximation ratio .
Organization of the paper.
In Section 2, we present some preliminaries needed for our results. Section 3 provides absolute approximation algorithms for 3d-bp and 3d-sp, and we prove Theorems 1 and 2. Section 4 deals with the asymptotic approximation algorithm for 3d-bp and establishes Theorem 5. In Section 5, we discuss results related to 3d-mvbb and prove Theorem 4. Section 6 provides absolute approximation guarantee for 3d-bp with rotation. Finally, Section 7 ends with a conclusion. Due to space constraints, most of the details have been shifted to the full version of the paper [39].
1.2 Related work
For , Caprara [12] gave an algorithm with AAR of for both -dimensional Bin Packing and Strip Packing. Sharma [54] gave -asymptotic approximation for these two problems when the items can be orthogonally rotated about all or a subset of axes. For 3d-mvbb, if the items are allowed to be rotated by 90 degrees about any axis, Alt and Scharf [6] gave a 17.738-approximation. Another related problem is the 3D Knapsack problem, in which each item additionally has an associated profit, and the goal is to obtain a maximum profit packing inside a unit cube knapsack. The authors in [19] have given a -approximation algorithm. For other related problems, we refer the readers to the surveys on approximation algorithms for multidimensional packing [5, 14].
2 Preliminaries
We define width, depth, and height along axes, respectively. Let be the given set of items, where each item is an axis-aligned cuboid having height, width, and depth equal to , respectively. Let be the maximum height, width, and depth of an item in , respectively. Given a box , if the (bottom-left-back corner of) item is placed (by translation) at then it occupies the region: , and the packing is feasible if . In this placement, we define the top, right, and back faces of item to be , , and , respectively. Analogously, bottom, left, and front faces are defined. Two items do not overlap if their interiors are disjoint. The volume of item is . For any set , let denote the total volume of items in . We define to be the value of the optimal solution for problem on instance .
2.1 Algorithms for 3D Packing
We now state three results on 3D packing that will be crucial for our results. The first two of them give a volume-based guarantee.
Theorem 6 ([43]).
Let be a set of 3D items where each item has height bounded by .
-
1.
All items in can be packed into a strip with base and height .
-
2.
If further each item has either width or depth (or both) not exceeding , then all items in can be packed inside a strip with base and height .
Theorem 7 ([49]).
Given a set of 3D items , there is a polynomial-time algorithm that places these items into at most bins.
The last result is regarding the asymptotic approximation of 3d-sp.
Theorem 8 ([34]).
Given a set of 3D items where each item has height bounded by , for any constant , there is a polynomial-time algorithm that returns a packing of into a strip of height at most .
3 Absolute 6-approximation for 3D-BP
In this section, our goal is to prove Theorem 1. Let be a large constant such that the algorithm of Caprara [12] already yields an absolute 6-approximation when . Our goal is to obtain a 6-approximation for the case when . Let , and be a sufficiently small constant. The following lemma follows from a standard shifting argument.
Lemma 9.
There exists a polynomial-time computable such that the total volume of the items that have at least one of the dimensions in the range is at most .
We classify the items depending on their dimensions: let be the items whose height, width and depth all exceed (called large items), be the items with height at most , be the remaining items having width at most and be the remaining items with depth at most . Finally, let be the remaining items each having at least one of the dimensions in the range . Note that owing to Lemma 9. We further classify the items of in a similar way – let be the items with height at most , be the remaining items with width at most , and .
In the remainder of the section, we prove the following result.
Proposition 10.
If there exists a packing of all items into bins, then a packing using at most bins can be computed in polynomial-time.
For this, we first show the following lemma, which follows from a simple application of Theorem 8 (see Figure 1 for an intuitive proof).
Lemma 11.
Let be a set of items each having a height (analogously width, depth) of at most , and suppose that there exists a packing of into bins. Then it is possible to compute a packing of using bins in polynomial-time. Further one of these bins has an empty strip with base and height (analogously width, depth) .
We divide the proof of Proposition 10 into two cases depending on .
3.1 Case 1:
In this case, for some , the total volume of the items in must not exceed – w.l.o.g. assume that . We first pack the items of and into bins each, using Lemma 11. Our goal next is to pack the items of into bins. To this end, we further classify the items of depending on their width and depth. Let and let . We first pack the items of into bins using the following lemma, by applying Theorem 6.
Lemma 12.
The items of can be completely packed into bins where each bin additionally has an empty strip with base and height .
Now consider the optimal packing inside bins restricted to the items of . Our goal is to compute a packing of all these items, barring a subset of items from that have a total volume of at most . For this, we first discretize the positions of the large items inside the bins. We focus on the packing inside any one bin.
Lemma 13.
By discarding items of having a total volume of at most , the number of distinct positions of the items of can be assumed to be polynomially-bounded.
Proof.
Let us start with the optimal packing inside bins restricted to the items of . For discretizing the - and -positions, we push all items as much to the left and front as possible. Then the distance of the left (resp. front) face of an item of from the left (resp. front) face of the bin can be written as the sum of the widths (resp. depths) of at most large items and at most one item of . Thus there are polynomially-many choices.
In order to discretize the positions along the -axis, we draw horizontal planes inside the bin at heights as integral multiples of and consider the large items inside the bin from bottom to top. For each in the order of increasing height of their bases, we discard items of in order to pull the item downwards, until the bottom face of hits one of the horizontal planes at heights multiples of or the top face of another large item lying below (see Figure 2). At the end of this process, it can be seen that the distance between the bottom face of any large item and the base of the bin can be written as the sum of a multiple of and the heights of at most items of . The total volume of the discarded items is bounded by .
We next draw horizontal planes passing through the top and bottom faces of each large item and discard the items of that are intersected by these planes. The volume of these discarded items is bounded by . This partitions the bin into at most slots, where each slot is penetrated from top to bottom by at most large items (see Figure 3). Note also that no large item begins or ends in the interior of a slot. Together with Lemma 13, we thus have the following result.
Lemma 14.
There exists a subset with such that the items of are completely packed inside the slots formed by the large items in the bins.
Our algorithm essentially tries to compute a packing close to the one guaranteed by the above lemma. As mentioned before, we obtain a packing into bins of all items of , and a large volume subset of that is packed inside the slots formed by the large items.
Lemma 15.
In polynomial-time, it is possible to compute a set with , and a packing of all items in into bins.
Proof.
We first guess the positions (from polynomially many choices) of all the (at most ) large items inside the bins, and create slots by extending their top and bottom faces. Our goal is to pack a maximum volume subset of into these slots by creating an instance of the Generalized Assignment Problem (GAP) with knapsacks, for which there exists a PTAS [25] (see Section A.3 for details). Each slot corresponds to a knapsack with capacity equal to the height of the slot. For an item , the size of for a slot equals its height if the item fits inside the slot, given the relative positions of the large items inside it, and otherwise. The profit of an item is the same as its volume. By Lemma 14, the optimal packing packs items of having a volume of at least . We apply the PTAS for GAP with parameter to our instance, yielding a packing of a subset into the slots formed by the items of , whose volume is least .
It remains to pack the items of and . Intuitively, they have a small volume, and hence we can pack them into the empty regions inside the already-existing bins.
Lemma 16.
The items of can be completely packed by using a height of from each of the empty regions inside the bins that were used to pack the items of . Further, the items in can be packed within a height of inside one of the bins.
Altogether, we used bins for packing items in and bins for packing the items of , resulting in at most bins overall.
3.2 Case 2:
In this case, we first pack the items of and into bins each, using Lemma 11 (note that these items have height, width and depth bounded by , respectively). Let be the bins having empty strips of height, width, and depth , respectively, that are guaranteed by Lemma 11. Intuitively, since the large items have a very small volume, they can be completely packed inside these empty strips.
Lemma 17.
The items in can be completely packed inside three strips, each having a base aligned with the -, - and -planes, respectively. The strips have height, width, and depth of , respectively, and therefore they fit inside the bins and .
Overall, we obtain a packing into bins, establishing Proposition 10.
Overall algorithm.
We first run the algorithm of Caprara [12] that already returns a 6-approximate solution when . Next, for each guessed value of , we run the algorithm of Proposition 10. For this, we first compute a value of using Lemma 9 and classify the items as discussed. Next, we divide into two cases depending on the volume of the large items. If , we find for which the volume of the items in does not exceed ; w.l.o.g we take . We pack the items of and into bins each using Lemma 11. We classify items of into and depending on their width and depth, and obtain a packing of into bins, ensuring each of these bins has an empty strip of height . Next we compute a set such that , and pack the items of into bins via a reduction to the Generalized Assignment Problem (Lemma 15). Finally, the items in are packed into the empty spaces inside the bins for using Lemma 16. For the other case when , we pack items in and into bins each, using Lemma 11, ensuring one of the bins has a sufficiently large empty strip, and then pack items of inside these empty strips using Lemma 17.
3.3 Implication on 3D-SP
We now establish Theorem 2. We use the following observation from our 3d-bp algorithm.
Lemma 18.
If there exists a packing of all items into a single bin, then it is possible to compute a packing into 6 bins in polynomial-time, where one of the bins is filled up to a height of at most .
Consider now the optimal Strip Packing of the input instance. Since the height of this packing must lie in , we can assume the optimal height to be of the form , by losing only a factor of . We scale the height of each item by the guessed height so that all items now fit inside a bin. Using Lemma 18, we compute a packing into 6 bins and stack these bins one on top of the other along the height, so that the resulting height of the packing is at most . This establishes Theorem 2 with .
The above result holds for the case when the strip is unbounded along the -axis. If instead the strip could be extended along any of the -, - or -axes and the goal were to minimize the length of the strip along that direction, then we improve further.
Lemma 19.
If there exists a packing of all items into a single bin, then for any , it is possible to compute a packing into 6 bins in polynomial-time, where one of the bins is filled up to a length (height/width/depth) of at most .
W.l.o.g. assume that one of the bins is filled up to height . Thus, stacking the bins along the -axis would be of height at most , implying the following result.
Corollary 20.
For any , there exists a polynomial-time -approximation for 3d-sp, if the strip can be extended along any of the -, - or -axes.
4 Asymptotic -approximation for 3D-BP
In this section, we prove Theorem 5 and present an improved asymptotic approximation algorithm for 3d-bp. We will utilize ideas from the algorithm for 3d-sp by Jansen and Prädel [34] which packs into strip height of . As mentioned earlier, the naive approach of cutting the strip at integral height will result in -approximation. Instead, we exploit the structural properties of the solution provided by the algorithm, along with the harmonically rounded heights of the items, to ensure that items with a height larger than are not sliced.
Recall the definition of harmonic rounding: For , , for ; and for . Also, if , then . In the following, we assume to be large enough such that , and define to be . See Section A.1 for more details on harmonic rounding.
Let be the instance derived from the given 3d-bp instance by applying harmonic rounding to the heights of the items. Thus an item becomes an item of with width, depth, height to be , respectively. Let denote the minimum number of bins with dimensions required to pack all items from , and let denote the minimum height to pack all items from into a strip with unit square base and unbounded height. The following lemma connects packing of with :
Lemma 21.
.
We transform the instance for 3d-sp into an instance for 2d-bp, similar to [34], which then uses structural results from a 2d-bp algorithm [35]. Given , we round up the item heights of to the next multiple of . We create an instance of 2d-bp, by introducing for each item with rounded height , exactly rectangles with width and depth . The following lemma bounds the incurred loss.
Lemma 22.
.
4.1 Essentials of the 2D-BP algorithm
The main ingredient for the 2d-bp algorithm by Jansen and Prädel [35] is a restructuring theorem. It states that each packing can be rearranged into packing with an iterable structure. This rearrangement comes at the cost of introducing more bins to the packing.
First, the items are classified into big, vertical, horizontal, intermediate, and tiny based on a suitably chosen constant . Let . An item is big if and ; vertical if but ; horizontal if but ; tiny if and ; and intermediate if either or . Using standard arguments, we can assume that the area of intermediate items is at most .
Jansen and Prädel [35] showed the existence of a structured packing called 2D-container-packing. In 2D-container-packing, one can consider a rounded-up instance from , where the widths and depths of big items, widths of horizontal items, and depths of vertical items from are rounded to values. Let be the set of different types of (rounded) large items, widths of wide items, and depths of vertical items in , respectively. Then is , and are . Furthermore, vertical items are allowed to be sliced along -axis, horizontal items may be sliced along -axis, and tiny items may be sliced in both directions. In 2D-container-packing, each bin of the packing is partitioned into at most containers and the widths and depths of containers come from possible values, see Figure 4. The containers are of five types, and only specific types of items from are allowed to be packed in the corresponding containers: (i) Big container: Each such container contains only one (rounded up) big item and has the size of this big item. Each bin contains at most such containers. (ii) Horizontal containers: each such container has a width and a depth that is a multiple of , and contains only horizontal items with rounded width . Each line along the -axis (depth) through the bin intersects at most horizontal containers. (iii) Vertical containers: each such container has a depth , a height that is a multiple of , and contains only vertical items with rounded depth . Each line along the -axis (width) through the bin intersects at most vertical containers. (iv) Tiny containers: Contains only tiny items and have a width and depth that is a multiple of . Each bin contains at most of these containers. (v) Intermediate containers: These containers contain only intermediate items. There will be an extra bins reserved separately to pack the intermediate items.
Let be the optimal 2D-container-packing for . Jansen and Prädel [35] showed the existence of a good 2D-container-packing.
Theorem 23 ([35]).
There exists a rounded up instance from such that the following holds: . Further, is one of possible roundings for the items , and given a subset , it is possible to decide in time if this set fits into a 2D-container-packing consisting of one bin.
A 2D-bin configuration is a vector that specifies a set of items that can be placed into one bin of a 2D-container-packing. This vector specifies for each big item type , the number of items of this type in the container; for each horizontal item width , the number where the total depth of containers for these items is ; for each vertical item depth , the number where the total width of containers for these items is ; and for tiny items, the number where the total area of containers for tiny items is . Let be the set of all 2D-bin configurations. Then is as the sum of entries has an upper bound of . By Theorem 23, we can verify in polynomial-time if a given vector translates to a configuration .
To find a 2D-container-packing, the algorithm from [35] utilizes an integer program, to find . However, for our purposes, the linear programming (LP) relaxation of this program is sufficient. For each big item type , let denote the number of items with this type. Similarly, let denote the total width of vertical items with rounded depth , and denote the total depth of horizontal items with rounded width . Further, let denote the total area of tiny items in . We introduce variables that denote for each configuration , the amount of this configuration in the solution, e.g., if , the configuration appears 2.7 times in the optimal LP solution. The LP is defined as follows.
Let denote the optimal solution for the LP. A basic solution to this LP uses only different configurations, as there are only types of containers in total.
Lemma 24.
and in time a basic solution with can be found.
Combining all the transformation steps (Lemma 21, Lemma 22, Theorem 23, and Lemma 24) to the 3d-bp instance results in Corollary 25.
Corollary 25.
.
4.2 The algorithm for 3D-BP
In this subsection, we describe how the items are filled into the bins when a solution to the configuration LP is given. An overview of the complete algorithm can be found in Algorithm 1. For each 2D configuration with , we create a 3D configuration of height , whose base is identical to . From Corollary 25, the sum of the heights of these configurations is at most . The 2D containers of raised by the corresponding height of the configuration will be referred to as 3D containers, and will be denoted by the same type as the corresponding 2D containers. Our goal is to pack the items of into these 3D containers while ensuring the tall-not-sliced property. We shall call the items with a rounded height larger than as tall, and the remaining items as short. The classification of items into big, vertical, horizontal, tiny, and intermediate depending to the dimensions of their top faces, as defined in the previous subsection continues to hold.
Placing big items.
The different slices of a 3D big item might be rounded differently by the 2d-bp algorithm. However, using a linear program we can assign almost all 3D big items into the 3D big containers, without violating the container heights.
Lemma 26.
In polynomial-time, it is possible to compute an assignment of all but big items into the 3D big containers, such that for each 3D big container, stacking the assigned items along the height does not exceed the height of the container.
The unassigned big items will be packed using additional bins. We now pack the big items assigned to a container, while ensuring the tall-not-sliced property. Assume that the base of the container is aligned with the -plane at height 0. We sort the tall items in non-increasing order of their heights, and stack the items of height (where ) one above the other, starting at the next available -coordinate that is a multiple of . Following this, we stack the short items in an arbitrary order above the tall items. Then it is easy to see that the gaps between the tall items sum up to at most , and therefore by increasing the height of the container by , we can pack all the assigned big items ensuring tall-not-sliced property.
Placing horizontal items.
Each 3D horizontal container is packed with horizontal items whose rounded width matches the container’s width. To ensure that all horizontal items are packed, the container height is increased by , and the depth is extended by . Since the container’s width is exactly the item width, we simplify the placement by considering only the -plane, i.e., the right face of the container/items (see Figure 4). These 2D objects are then packed using a variant of the NFDH algorithm: shelves containing an item of height are positioned at -coordinates that are multiples of . As a consequence, shelves containing a tall item never overlap an integer height. The total gaps between shelves sum to . Given the large enough height increase of , standard analysis of the NFDH algorithm ensures that all horizontal items fit into the containers (see Section A.2). Finally, the depth extension of the containers has to be reverted. Items that are (partly) placed inside the extended depth are repacked into containers by leveraging the fact that each line parallel to the -axis intersects at most horizontal containers, and each horizontal item has a depth of at most .
Lemma 27.
Enlarging the height of the 3D horizontal containers by allows all horizontal items to be placed into their containers and at most additional bins while maintaining the tall-not-sliced property.
The vertical items are packed analogously into the 3D vertical containers. The tiny items are packed using a variant of NFDH into the 3D tiny containers and few additional bins.
Lemma 28.
By enlarging the 3D tiny containers by along the height, it is possible to compute a packing of a subset of the tiny items ensuring the tall-not-sliced property. The remaining tiny items can be packed into additional bins.
We use Theorem 7 to place the medium items into additional bins, as they have a volume of at most . Note that the heights of all the 3D containers were extended by in order to obtain a tall-not-sliced packing. Since the number of configurations was , the height of the packing only increases by . Let be the height of the stacked extended 3D-configurations returned by the algorithm. We create bins by cutting this packing at integer heights. The items sliced by this process all have a height of at most , and, hence, we can pack items sliced at heights inside a single bin. Together with the additional bins used for packing the big, horizontal, vertical and tiny items, the number of bins needed is at most , establishing Theorem 5.
5 Algorithms for 3D-MVBB
In this section, we establish Theorem 4. Note that by the discussion in Section 3, Corollary 20 already implies an absolute approximation ratio of for 3d-mvbb, improving on the result of [43]. We now improve the approximation factor to . First, as previously described, we guess the dimensions of the optimal bounding box within factors of , and then scale the dimensions of each item by the corresponding (guessed) dimensions of the bounding box, so that all items now fit inside a bin.
Absolute approximation.
We compute a value of such that the volume of the (scaled) items that have at least one of the dimensions in the range is bounded by , and classify the items into and as in Section 3. The items in are further classified into the sets and which can be packed into strips of thickness using the following lemma.
Lemma 29.
The items of (resp. ) can be packed inside a strip with base and height (resp. width, depth) at most .
We now consider the packing of the items in and obtain the following result.
Proposition 30.
In polynomial-time, we can compute a packing of inside a cubic bin of side length .
The main idea behind the above result is to use Strip Packing with resource augmentation – if the width and depth of the strip are extended by a factor of , we can use a result of Bansal et al. [8] for 2d-bp, which returns a packing into the optimal number of bins where the sides of each bin are extended by a factor of . For this, we first discretize and guess the positions of all items in (at most ) inside the bin, and then obtain a set of 3D configurations that respect the positions of the items of , into which items of are packed fractionally. Finally, using the techniques described in Section 4, we can obtain an integral packing of by increasing the height of each configuration by the maximum height . This results in an overall increase in height of .
Proposition 30 also directly yields packings of and into bins of size . Together with Lemma 29, we obtain a packing of all input items into a bounding box of volume , establishing the absolute approximation guarantee of Theorem 4.
APTAS.
In order to obtain an APTAS for 3d-mvbb, we notice that the technique described above yields an APTAS for 3d-sp when the base of the strip can be augmented by . We run this Strip Packing algorithm with the base of the strip aligned along the -, - and -planes, respectively, thus obtaining three bounding boxes, and return the one with the minimum volume. We show in the full version [39] that this gives an APTAS.
6 3D-BP with rotations
In this section, we present a 5-approximation for 3d-bp when the items are allowed to be rotated by about any axis (Theorem 3).
Proof of Theorem 3.
The work of Sharma [54] gave a -asymptotic approximation for 3d-bp with rotations, building on the algorithm of Caprara [12]. Let be a large constant so that the algorithm of Sharma gives an absolute approximation ratio of 5 when . From now on, we assume , and that we have correctly guessed the value of . Our goal is to obtain a packing of all items using at most bins. Define and let be the items having all dimensions exceeding , which we will refer to as the large items from now on.
We create groups of items from , where each group has a volume of at most . Each such group can be packed into a single bin using Theorem 6 since . If all items of are already packed, we pack the items of into an additional bins by brute-force enumeration, thus obtaining a packing of into bins, and are done. Otherwise, since the volume of each item in is bounded by , the volume of the items packed into each bin is at least , and we have packed a volume of at least . Let denote the set of unpacked items of . Note that since , we have .
Claim 31.
One of the dimensions of each item of does not exceed .
Proof.
Since , every large item must have a side of length at most .
We orient each large item so that its height is at most . Using Theorem 6, the large items can be packed inside a strip with base and height . Finally, the items of are also packed in a strip of height at most using Theorem 6. Thus the items in can all be packed inside a single bin. Overall, we obtain a packing of into bins, and are done.
7 Conclusion
We obtained improved approximation for . Our framework is quite general and should extend to other cases. E.g., for the case with rotations, we expect that our techniques should be easily extendable to provide similar asymptotic guarantees. We also expect that the asymptotic approximation algorithm for 3d-bp should extend to -dimensions () and provide a -approximation. The existence of a PTAS (or hardness) for 3d-mvbb is still open. It is also interesting to obtain improved guarantees in pseudopolynomial-time (when the input numeric data is polynomially bounded in ).
References
- [1] ICRA virtual manufacturing automation competition. https://www.icra2013.org/index0c2d.html?page_id=231.
- [2] OPTIL.io. https://www.optil.io/optilion/problem/3017.
- [3] Sara Ali, António Galrão Ramos, Maria Antónia Carravilla, and José Fernando Oliveira. On-line three-dimensional packing problems: A review of off-line and on-line solution approaches. Computers & Industrial Engineering, 168:108–122, 2022.
- [4] Sam D Allen, Edmund K Burke, and Graham Kendall. A hybrid placement strategy for the three-dimensional strip packing problem. European Journal of Operational Research, 209(3):219–227, 2011. doi:10.1016/j.ejor.2010.09.023.
- [5] Helmut Alt. Computational aspects of packing problems. Bulletin of EATCS, 1(118), 2016.
- [6] Helmut Alt and Nadja Scharf. Approximating smallest containers for packing three-dimensional convex objects. International Journal of Computational Geometry & Applications, 28(2):111–128, 2018. doi:10.1142/S0218195918600026.
- [7] Nikhil Bansal, Alberto Caprara, and Maxim Sviridenko. A new approximation method for set covering problems, with applications to multidimensional bin packing. SIAM Journal on Computing, 39(4):1256–1278, 2010. doi:10.1137/080736831.
- [8] Nikhil Bansal, José R Correa, Claire Kenyon, and Maxim Sviridenko. Bin packing in multiple dimensions: inapproximability results and approximation schemes. Mathematics of Operations Research, 31(1):31–49, 2006. doi:10.1287/moor.1050.0168.
- [9] Nikhil Bansal, Xin Han, Kazuo Iwama, Maxim Sviridenko, and Guochuan Zhang. A harmonic algorithm for the 3d strip packing problem. SIAM Journal on Computing, 42(2):579–592, 2013. doi:10.1137/070691607.
- [10] Nikhil Bansal and Arindam Khan. Improved approximation algorithm for two-dimensional bin packing. In SODA, pages 13–25, 2014. doi:10.1137/1.9781611973402.2.
- [11] Eberhard E Bischoff and Michael D Marriott. A comparative evaluation of heuristics for container loading. European Journal of Operational Research, 44(2):267–276, 1990.
- [12] Alberto Caprara. Packing d-dimensional bins in d stages. Mathematics of Operations Research, 33(1):203–215, 2008. doi:10.1287/moor.1070.0289.
- [13] Miroslav Chlebík and Janka Chlebíková. Hardness of approximation for orthogonal rectangle packing and covering problems. Journal of Discrete Algorithms, 7(3):291–305, 2009. doi:10.1016/j.jda.2009.02.002.
- [14] Henrik I Christensen, Arindam Khan, Sebastian Pokutta, and Prasad Tetali. Approximation and online algorithms for multidimensional bin packing: A survey. Computer Science Review, 24:63–79, 2017. doi:10.1016/j.cosrev.2016.12.001.
- [15] Edward G Coffman, Jr, Michael R Garey, David S Johnson, and Robert Endre Tarjan. Performance bounds for level-oriented two-dimensional packing algorithms. SIAM Journal on Computing, 9(4):808–826, 1980. doi:10.1137/0209062.
- [16] Teodor Gabriel Crainic, Guido Perboli, and Roberto Tadei. Extreme point-based heuristics for three-dimensional bin packing. INFORMS Journal on Computing, 20(3):368–384, 2008. doi:10.1287/ijoc.1070.0250.
- [17] Teodor Gabriel Crainic, Guido Perboli, and Roberto Tadei. Ts2pack: A two-level tabu search for the three-dimensional bin packing problem. European Journal of Operational Research, 195(3):744–760, 2009. doi:10.1016/j.ejor.2007.06.063.
- [18] János Csirik and André Van Vliet. An on-line algorithm for multidimensional bin packing. Operations Research Letters, 13(3):149–158, 1993. doi:10.1016/0167-6377(93)90004-Z.
- [19] Florian Diedrich, Rolf Harren, Klaus Jansen, Ralf Thöle, and Henning Thomas. Approximation algorithms for 3d orthogonal knapsack. Journal of Computer Science and Technology, 23(5):749–762, 2008. doi:10.1007/s11390-008-9170-7.
- [20] Thai Ha Duong. Heuristics approaches for three-dimensional strip packing and multiple carrier transportation plans. PhD thesis, University of Nottingham, 2015.
- [21] Leah Epstein and Rob van Stee. Optimal online bounded space multidimensional packing. In SODA, pages 214–223, 2004. URL: http://dl.acm.org/citation.cfm?id=982792.982823.
- [22] Oluf Faroe, David Pisinger, and Martin Zachariasen. Guided local search for the three-dimensional bin-packing problem. INFORMS journal on Computing, 15(3):267–283, 2003. doi:10.1287/ijoc.15.3.267.16080.
- [23] Carlos E Ferreira, Flavio K Miyazawa, and Yoshiko Wakabayashi. Packing squares into squares. Pesquisa Operacional, 19(2):223–237, 1999.
- [24] Lisa Fleischer, Michel X Goemans, Vahab S Mirrokni, and Maxim Sviridenko. Tight approximation algorithms for maximum separable assignment problems. Mathematics of Operations Research, 36(3):416–431, 2011. doi:10.1287/moor.1110.0499.
- [25] Waldo Gálvez, Fabrizio Grandoni, Salvatore Ingala, Sandy Heydrich, Arindam Khan, and Andreas Wiese. Approximating geometric knapsack via L-packings. ACM Transactions on Algorithms, 17(4):1–67, 2021. doi:10.1145/3473713.
- [26] John A George and David F Robinson. A heuristic for packing boxes into a container. Computers & Operations Research, 7(3):147–156, 1980. doi:10.1016/0305-0548(80)90001-5.
- [27] Paul C Gilmore and Ralph E Gomory. Multistage cutting stock problems of two and more dimensions. Operations Research, 13(1):94–120, 1965.
- [28] Rolf Harren. Approximation algorithms for orthogonal packing problems for hypercubes. Theoretical Computer Science, 410(44):4504–4532, 2009. doi:10.1016/j.tcs.2009.07.030.
- [29] Rolf Harren, Klaus Jansen, Lars Prädel, and Rob Van Stee. A (5/3+ )-approximation for strip packing. Computational Geometry, 47(2):248–267, 2014. doi:10.1016/j.comgeo.2013.08.008.
- [30] Rolf Harren, Klaus Jansen, Lars Praedel, Ulrich M Schwarz, and Rob van Stee. Two for one: tight approximation of 2d bin packing. International Journal of Foundations of Computer Science, 24(08):1299–1327, 2013. doi:10.1142/S0129054113500354.
- [31] Sören Henning, Klaus Jansen, Malin Rau, and Lars Schmarje. Complexity and inapproximability results for parallel task scheduling and strip packing. Theory of Computing Systems, 64(1):120–140, 2020. doi:10.1007/s00224-019-09910-6.
- [32] Mhand Hifi, Imed Kacem, Stéphane Nègre, and Lei Wu. A linear programming approach for the three-dimensional bin-packing problem. Electronic Notes in Discrete Mathematics, 36:993–1000, 2010. doi:10.1016/j.endm.2010.05.126.
- [33] Klaus Jansen, Arindam Khan, Marvin Lira, and K. V. N. Sreenivas. A PTAS for packing hypercubes into a knapsack. In ICALP, pages 78:1–78:20, 2022. doi:10.4230/LIPIcs.ICALP.2022.78.
- [34] Klaus Jansen and Lars Prädel. A new asymptotic approximation algorithm for 3-dimensional strip packing. In SOFSEM, pages 327–338, 2014. doi:10.1007/978-3-319-04298-5_29.
- [35] Klaus Jansen and Lars Prädel. New approximability results for two-dimensional bin packing. Algorithmica, 74:208–269, 2016. doi:10.1007/s00453-014-9943-z.
- [36] Klaus Jansen and Malin Rau. Closing the gap for pseudo-polynomial strip packing. In ESA, pages 62:1–62:14, 2019. doi:10.4230/LIPIcs.ESA.2019.62.
- [37] Klaus Jansen and Roberto Solis-Oba. An asymptotic approximation algorithm for 3 d-strip packing. In SODA, pages 143–152, 2006. URL: http://dl.acm.org/citation.cfm?id=1109557.1109575.
- [38] Zhihong Jin, Takahiro Ito, and Katsuhisa Ohno. The three-dimensional bin packing problem and its practical algorithm. JSME International Journal Series C Mechanical Systems, Machine Elements and Manufacturing, 46(1):60–66, 2003.
- [39] Debajyoti Kar, Arindam Khan, and Malin Rau. Improved approximation algorithms for three-dimensional bin packing. arXiv preprint arXiv:2503.08863, 2025. doi:10.48550/arXiv.2503.08863.
- [40] Claire Kenyon and Eric Rémila. A near-optimal solution to a two-dimensional cutting stock problem. Mathematics of Operations Research, 25(4):645–656, 2000. doi:10.1287/moor.25.4.645.12118.
- [41] C. C. Lee and D. T. Lee. A simple on-line bin-packing algorithm. Journal of the ACM, 32(3):562–572, 1985. doi:10.1145/3828.3833.
- [42] Keoin Li and Kam Hoi Cheng. Heuristic algorithms for on-line packing in three dimensions. Journal of Algorithms, 13(4):589–605, 1992. doi:10.1016/0196-6774(92)90058-K.
- [43] Keqin Li and Kam-Hoi Cheng. On three-dimensional packing. SIAM Journal on Computing, 19(5):847–867, 1990. doi:10.1137/0219059.
- [44] Xueping Li, Zhaoxia Zhao, and Kaike Zhang. A genetic algorithm for the three-dimensional bin packing problem with heterogeneous bins. In IIE Annual Conference, page 2039, 2014.
- [45] Andrea Lodi, Silvano Martello, and Daniele Vigo. Heuristic algorithms for the three-dimensional bin packing problem. European Journal of Operational Research, 141(2):410–420, 2002. doi:10.1016/S0377-2217(02)00134-0.
- [46] Yiping Lu, Danny Z Chen, and Jianzhong Cha. Packing cubes into a cube is np-complete in the strong sense. Journal of Combinatorial Optimization, 29:197–215, 2015. doi:10.1007/s10878-013-9701-1.
- [47] Daniel Mack and Andreas Bortfeldt. A heuristic for solving large bin packing problems in two and three dimensions. Central European Journal of Operations Research, 20:337–354, 2012. doi:10.1007/s10100-010-0184-1.
- [48] Batoul Mahvash, Anjali Awasthi, and Satyaveer Chauhan. A column generation-based heuristic for the three-dimensional bin packing problem with rotation. Journal of the Operational Research Society, 69(1):78–90, 2018. doi:10.1057/s41274-017-0186-7.
- [49] Silvano Martello, David Pisinger, and Daniele Vigo. The three-dimensional bin packing problem. Operations Research, 48(2):256–267, 2000. doi:10.1287/opre.48.2.256.12386.
- [50] Aram Meir and Leo Moser. On packing of squares and cubes. Journal of Combinatorial Theory, 5(2):126–134, 1968.
- [51] Flavio Keidi Miyazawa and Yoshiko Wakabayashi. An algorithm for the three-dimensional packing problem with asymptotic performance analysis. Algorithmica, 18(1):122–144, 1997. doi:10.1007/BF02523692.
- [52] Flavio Keidi Miyazawa and Yoshiko Wakabayashi. Packing problems with orthogonal rotations. In LATIN, pages 359–368, 2004.
- [53] Francisco Parreño, Ramón Alvarez-Valdés, José Fernando Oliveira, and José Manuel Tamarit. A hybrid grasp/vnd algorithm for two-and three-dimensional bin packing. Annals of Operations Research, 179:203–220, 2010. doi:10.1007/s10479-008-0449-4.
- [54] Eklavya Sharma. Harmonic algorithms for packing d-dimensional cuboids into bins. In FSTTCS, pages 32:1–32:22, 2021. doi:10.4230/LIPIcs.FSTTCS.2021.32.
- [55] Tony Wauters, Jannes Verstichel, and Greet Vanden Berghe. An effective shaking procedure for 2d and 3d strip packing problems. Computers & Operations Research, 40(11):2662–2669, 2013. doi:10.1016/j.cor.2013.05.017.
- [56] Lijun Wei, Wee-Chong Oon, Wenbin Zhu, and Andrew Lim. A reference length approach for the 3d strip packing problem. European Journal of Operational Research, 220(1):37–47, 2012. doi:10.1016/j.ejor.2012.01.039.
Appendix A Tools and techniques
A.1 Harmonic transformation
Lee and Lee [41] introduced harmonic transformation in the context of online bin packing.
The harmonic transformation with parameter is defined by the following function :
For , , for .
Otherwise, .
Intuitively, the function rounds up
to the nearest larger number of the form where .
Now we define harmonic constant . Let and for . The sequence is also known as Sylvester’s sequence (where each term is the product of the previous terms, plus one). Let be the integer such that . Now is defined as , and . Thus . Note that .
Lee and Lee [41] showed that that, for any sequence , with and , we have . In fact, .
In fact, Bansal, Han, Iwama, Sviridenko, and Zhang [9] showed the above inequality is true even if we define for .
A.2 Next-Fit-Decresing-Height (NFDH)
The Next-Fit-Decreasing-Height (NFDH) algorithm is a shelf-based approach for packing 2D items into a strip of fixed width . Given a set of items , the algorithm first sorts them in decreasing order of height. It then places the items sequentially from left to right on the floor of the strip (or the current shelf) until the next item no longer fits, i.e., adding the next item would cause the total width of items on the shelf to exceed . At this point, a new shelf is created by drawing a horizontal line at the height of the tallest item on the current shelf. The process then continues on the new shelf, following the same placement rule, until all items have been packed. For more details on the algorithm, we refer to [15, 14].
Lemma 32 ([15]).
Given a 2D rectangular box of height and width , and a set of 2D items with maximum height and maximum width , it is possible to place any subset of items with a total area of at most , into the box using NFDH.
A.3 Generalized Assignment Problem (GAP)
In the Generalized Assignment Problem, we are given a set of knapsacks each with an associated capacity , and a set of items, where each item has size and profit for knapsack . The goal is to obtain a maximum-profitable packing of a subset of the items into the knapsacks, that respects the knapsack capacities, i.e., the total size of the items packed inside each knapsack do not exceed the capacity of the knapsack. For the general case of GAP, there is a tight -approximation [24]. However for the special case when , there exists a PTAS.
Theorem 33 ([25]).
For any , there is an algorithm for GAP with knapsacks running in time, that returns a packing of profit at least .