Improved Approximation Algorithms for Three-Dimensional Knapsack

In this paper, we introduce container packing for 3D Knapsack. We show that we can divide the 3D knapsack into $O(1)$ number of regions (called containers) such that the dimensions of these containers come from a polynomial-sized set. For each container $C$ we define its capacity $\mathrm{𝚌𝚊𝚙}(C)\in {\mathbb{Q}}_{\ge 0}$ and for each item $i$ we define its size in $C$ to be $f_C(i)\in {\mathbb{Q}}_{\ge 0}$. We also associate an algorithm ${𝒜}_C$ for the container. We require ${𝒜}_C,f_C$ such that for any $C$ and any set of items $T$ satisfying the packing constraint ${\sum }_{i\in T}{f}_C(i)\le \mathrm{𝚌𝚊𝚙}(C)$, almost all items in $T$ (barring a small profit subset) can be packed into $C$ by algorithm ${𝒜}_C$. The assignment of items into containers thus becomes a variant of the Multiple Knapsack problem (however, the knapsacks can have different capacities and items can have sizes specific to the knapsacks) – also a special case of Generalized Assignment Problem (GAP). For $O(1)$ knapsacks, there exists a PTAS for GAP [11]. After the assignment of items to the container $C$, the corresponding algorithm ${𝒜}_C$ ensures that the items admit a feasible profitable packing.

Container packing is a powerful and general technique. For example, by choosing appropriate functions $f_C$, our containers can handle complicated packings, beyond simple greedy algorithms. For example, we use six different types of containers in this work (see Figures 4 and 8). Apart from the Stack containers and Volume containers (similar to 2D packing), we introduce Area containers (packed using a variant of Next-Fit-Decreasing-Height (NFDH) algorithm [9]), Steinberg containers (where different types of items are packed together using our new volume-based packing algorithm 3D-Vol-Pack – it packs items in layers where each layer is packed using either a greedy algorithm or a 2D packing algorithm called Steinberg’s algorithm [26]), and $𝖫$-Containers (where two different types of stacks are packed together when rotations are allowed). Note that Steinberg container or $𝖫$-Container goes beyond simple stack or shelf-based algorithms and equips us to handle more complicated packings of different types of items. Finally, we show that given an optimal packing, we can modify it to some container packing having significant profit. The functions $f_C$ can be considered analogous to the weighting functions in bin packing [9], and we expect that more complicated packing algorithms can be incorporated into this framework by suitably defining $f_C$.

Using this, we obtain improved approximation guarantees for 3DK (see Table 1). In particular, we obtain $(139/29+\epsilon )$-approximation for 3DK and $(30/7+\epsilon )$-approximation for 3DKR (when rotations by 90 degrees are allowed around all axes). For the cardinality case (when all items have the same profit), we obtain $17/4+\epsilon$ and $24/7+\epsilon$, respectively, for the cases without and with rotations. Finally, in the case when the profit of an item is equal to its volume (also called uniform profit-density), we obtain approximation guarantees of $4+\epsilon$ and $3+\epsilon$, without and with rotations, respectively.

Due to space limitations, some parts of the proofs are omitted in this extended abstract. For missing details, we refer the reader to the full version [16].

Two other related problems are 3D Bin Packing (BP) and Strip Packing (SP). In 3D BP, given a set of cuboids and unit cubes as bins, the goal is to find a nonoverlapping axis-aligned packing of all items into the minimum number of bins. In 3D SP, given a set of cuboids, the goal is to pack them into a single 3D rectangular box of unlimited height such that the height of the packing is minimized. For 3D BP and 3D SP, the best-known (asymptotic) approximation ratios are $T_{\mathrm{\infty }}^2\approx 2.86$ [6] and $3/2+\epsilon$ [19], respectively. For more details on related problems, we refer the readers to surveys [2, 8] on approximation and online algorithms for multidimensional packing.

We now describe a few procedures that we repeatedly use throughout the paper to pack items. For a cuboidal box $B$, let $w_B,d_B,h_B$ denote the width, depth, and height of $B$, respectively. The volume of the box is then $v(B)=w_B\times d_B\times h_B$.

We now describe the various types of containers that we use to pack items. For a container $C$, its width, depth, and height are denoted by $w_C,d_C$, and $h_C$, respectively, and its volume $v(C):=w_C\times d_C\times h_C$. For each container $C$, we specify its capacity $\mathrm{𝚌𝚊𝚙}(C)$, the function $f_C,$ and the packing algorithm ${𝒜}_C$. Let $T$ denote the set of items assigned to $C$ such that ${\sum }_{i\in T}{f}_C(i)\le \mathrm{𝚌𝚊𝚙}(C)$. We suggest the reader to follow the descriptions alongside Figure 4.

• $\mathrm{■}$

  Stack containers: These containers pack items in layers, with one item in each layer. We consider a container $C$ that stacks items along the height. See container ($1a$) in Figure 4. The capacity $\mathrm{𝚌𝚊𝚙}(C)$ of such a container is set to its height $h_C$, and for any item $i$, $f_C(i):=h_i$ if $w_i\le w_C$ and $d_i\le d_C$, and $f_C(i):=\mathrm{\infty }$ otherwise.

  ${𝒜}_C$ just stacks the items of set $T$ in the container $C$ one above the other. Analogously containers ($1b$) and ($1c$) show containers that stack along width and depth, respectively.

• $\mathrm{■}$

  Area containers: Inside these containers, the items are packed using the NFDH algorithm, by ignoring one of the dimensions. We describe Area containers that use NFDH along the front face of the container (see container ($2a$)). For such a container $C$, we set $\mathrm{𝚌𝚊𝚙}(C):=w_C{h}_C$, and for any item $i$, we set $f_C(i):=w_i{h}_i$ if $w_i\le \epsilon w_C$, $h_i\le \epsilon h_C$ and $d_i\le d_C$, and $f_C(i):=\mathrm{\infty }$ otherwise.

  ${𝒜}_C$ first sorts the items of set $T$ in non-increasing order of profit/front area ratio. Then, we select the largest prefix whose total front area does not exceed $(1-2\epsilon )w_C{h}_C$. We pack this prefix using NFDH on the front face. Analogously, container ($2b$) and ($2c$) show packing when NFDH is used on the left and bottom face of $C$, respectively.

• $\mathrm{■}$

  Volume containers: The items are packed using 3D-NFDH inside these containers (see container (3)). The capacity of such a container $C$ is set to be its volume $v(C)$, and $f_C(i):=v(i)$ if $w_i\le \epsilon w_C$, $d_i\le \epsilon d_C$ and $h_i\le \epsilon h_C$, and $f_C(i):=\mathrm{\infty }$ otherwise.

  ${𝒜}_C$ sorts the items of $T$ in non-decreasing order of profit/volume and selects the largest prefix with volume not exceeding $(1-3\epsilon )w_C{h}_C{d}_C$. We pack this prefix using 3D-NFDH.

• $\mathrm{■}$

  Steinberg containers: These containers pack items in layers using 3D-Vol-Pack. We describe Steinberg containers that pack items in layers along the height (analogous for other cases). We set $\mathrm{𝚌𝚊𝚙}(C):=v(C)/3$. For any item $i$, we set $f_C(i):=v(i)$ if $h_i\le \epsilon h_C$, and either $w_i\le w_C/2$ or $d_i\le d_C/2$ holds. For all other items, we set $f_C(i):=\mathrm{\infty }$.

  ${𝒜}_C$ first sorts the items in $T$ in non-increasing order of profit/volume ratio. Then, we select the largest prefix whose volume does not exceed $\left(\frac{1}{3}-2\epsilon \right)v(C)$, and pack this prefix using 3D-Vol-Pack. Analogously, container ($4b$) and ($4c$) show packing when layers are stacked along the depth and width, respectively.

Let ${\mathrm{𝚘𝚙𝚝}}_{\mathrm{gs}}$ be the maximum profit of a guessable container packing. The main structural result of our paper is the following.

Together with Theorem 7, this gives us the following theorem.

We prove Lemma 8 in Section 4 by establishing several lower bounds on ${\mathrm{𝚘𝚙𝚝}}_{\mathrm{gs}}$. Specifically, we present five different ways to restructure OPT into a guessable container packing. Our first lower bound is based on a structural result of the 3D Strip Packing problem due to [19]. The second lower bound is obtained by restructuring the packing of items in $\text{OPT}\cap (I_{1\mathrm{\ell }}\cup L)$ (or similarly $\text{OPT}\cap (I_{2\mathrm{\ell }}\cup L)$ or $\text{OPT}\cap (I_{3\mathrm{\ell }}\cup L$)). The third and fourth lower bounds are based on volume-based arguments, using our simple packing algorithm 3D-Vol-Pack. Our final lower bound is based on a structural result from the 2D Knapsack problem [11].

We consider the packing of the items in $\text{OPT}\cap I_1$ (i.e., items with height at most $\mu$) whose total profit is ${\mathrm{𝚘𝚙𝚝}}_1$. We build on the structure derived from the 3D Strip Packing algorithm of Jansen and Prädel [19]. However, we need several refinements to transform the packing of [19] into a guessable container packing.

First, using standard arguments, we discard a set of (medium) items (items whose widths or depths lie in the range $[{\delta }^{10},\delta )$ for a suitably chosen $\delta$) at a $(1+\epsilon )$-factor loss in the approximation ratio. Then the items are divided into four classes depending on their dimensions. An item $i$ is big if both $w_i\ge \delta$ and $d_i\ge \delta$, wide if $w_i\ge \delta$ and , long if and $d_i\ge \delta$, and small if both and . The following lemma is obtained by an adaptation of the result of [19] (see Figure 6).

Our objective is to build Area and Volume containers out of the slots for packing the wide/long and small items, respectively. The trouble is that the slot dimensions might not be large enough compared to the dimensions of the packed items, which is a necessary condition for the construction of such containers (see Section 3.1). We obtain a guessable container packing by the following lemma.

After applying the above lemma, the rounded heights of all the configurations for $T_1$ sum up to at most $(1-2\epsilon )+\frac{\mu }{\epsilon }\cdot O(\frac{1}{{\delta }^6})\le 1-\epsilon$, for sufficiently small $\mu$. Since items of $T_2$ are packed inside a Steinberg container of height $\epsilon$, all the containers fit inside the knapsack and we obtain the following theorem overall.

An equivalent restructuring of $\text{OPT}\cap I_2$ and $\text{OPT}\cap I_3$ gives the following corollary.

We now present a simple $(5+\epsilon )$-approximation for 3DK, which already improves upon the $(7+\epsilon )$-approximation [10]. For this, first, we provide the following packing guarantee.

Then the following lemma, together with Theorem 7, gives a $(5+\epsilon )$-approximation.

In this subsection, we consider the packing of $\mathrm{OPT}\cap (I_{1\mathrm{\ell }}\cup L)$, and restructure it to obtain a guessable container packing, by losing only an $O(\epsilon )$-fraction of the profit. Let ${\text{OPT}}_{1\mathrm{\ell }}:=\mathrm{OPT}\cap I_{1\mathrm{\ell }}$ and ${\text{OPT}}_L:=\mathrm{OPT}\cap L$. Since each item in $L$ has all side lengths at least $\mu$, the number of such items in the packing is $|{\text{OPT}}_L|\le 1/{\mu }^3$. Also, since the width and depth of each item in $I_{1\mathrm{\ell }}$ is at least 1/2, the items of ${\text{OPT}}_{1\mathrm{\ell }}$ must be packed in layers, i.e., the top and bottom faces of any item in ${\text{OPT}}_{1\mathrm{\ell }}$ when extended parallel to the bottom face of the knapsack will not intersect another item from ${\text{OPT}}_{1\mathrm{\ell }}$. We now discretize the positions of the items in the packing.

Let $T\subseteq {\text{OPT}}_{1\mathrm{\ell }}$ be the $k$ items of largest profit in ${\text{OPT}}_{1\mathrm{\ell }}$, for some $k$ to be chosen later. Our goal is to obtain a container packing of all items in ${\text{OPT}}_L$, together with a subset of ${\text{OPT}}_{1\mathrm{\ell }}$ having a profit of at least $(1-\epsilon ){\mathrm{𝚘𝚙𝚝}}_{1\mathrm{\ell }}$. To this end, we shall pack all items in $T$ and ensure that the number of discarded items of ${\text{OPT}}_{1\mathrm{\ell }}$ is bounded by $ck$, for some constant $c$. By a result of [18], the profit of the discarded items can be bounded by $\epsilon {\mathrm{𝚘𝚙𝚝}}_{1\mathrm{\ell }}$, for appropriately chosen $k$. We now outline the details of our restructuring procedure. See Figure 7.

We draw horizontal planes passing through the top and bottom faces of the items in $T\cup {\text{OPT}}_L$, and discard the items of ${\text{OPT}}_{1\mathrm{\ell }}\setminus T$ intersecting these planes (see Figure 7). The number of discarded items is bounded by $2|{\text{OPT}}_L|=O(1/{\mu }^3)$. The remaining items of ${\text{OPT}}_{1\mathrm{\ell }}\setminus T$ are now completely packed inside at most $k+2|{\text{OPT}}_L|+1$ horizontal strips demarcated by the planes. Each such strip is a cuboidal box that is pierced from top to bottom by at most $1/{\mu }^2$ Large items. Further, there are only polynomially-many positions of these Large items inside the strip owing to Lemma 16. We focus on one such strip $𝒮$.

For each item in $T\cup {\text{OPT}}_L$, we create a Stack container containing the single item itself. Together with Lemma 17, we get $O_{\mu }(1)$ number of Stack containers inside the knapsack. We now discretize the heights of the Stack containers, so that they lie in a polynomial-sized set.

Together with the $O(1/{\mu }^3)$ items that were discarded previously, Lemma 18 gives us that the total number of discarded items so far is at most $O(1/{\mu }^{11})k$. We now use the following lemma from [18].

The above lemma invoked with $c=O(1/{\mu }^{11})$ and with the correct guess of $k$ gives us that the total profit of the discarded items is at most $\epsilon {\mathrm{𝚘𝚙𝚝}}_{1\mathrm{\ell }}$, assuming that $|{\text{OPT}}_{1\mathrm{\ell }}|$ was sufficiently large (at least $n_0:={(1/\mu )}^{\mathrm{\Omega }(1/\epsilon )}$) to begin with (otherwise, it is trivial). The following theorem summarizes the arguments of this section.

In this subsection, we restructure the packing of items in $\text{OPT}\cap I_1$. Recall that ${\mathrm{𝚘𝚙𝚝}}_{1\mathrm{\ell }}=p(\text{OPT}\cap I_{1\mathrm{\ell }})$ and ${\mathrm{𝚘𝚙𝚝}}_{1s}=p(\text{OPT}\cap I_{1s})$, so that ${\mathrm{𝚘𝚙𝚝}}_{1\mathrm{\ell }}+{\mathrm{𝚘𝚙𝚝}}_{1s}={\mathrm{𝚘𝚙𝚝}}_1$. Also, $v_1:=v(\text{OPT}\cap I_1)$ and $v_{1s}=v(\text{OPT}\cap I_{1s})$.

In the previous sections, we repacked items from exactly one set out of $I_1,I_2,I_3$. In this subsection, we restructure the packing of a subset of items from $I_1$, together with items from $I_2\cup I_3\cup L$. To this end, we introduce a classification of the items in $I_2\cup I_3\cup L$. Let $S_2$ (resp. $S_3,S$) be the set of items in $I_2$ (resp. $I_3,L$) with height at most 1/2. Define ${\mathrm{𝚘𝚙𝚝}}_{2t}:=p(\text{OPT}\cap S_2)$ and ${\mathrm{𝚘𝚙𝚝}}_{2h}:=p(\text{OPT}\cap (I_2\setminus S_2))$, so that ${\mathrm{𝚘𝚙𝚝}}_{2t}+{\mathrm{𝚘𝚙𝚝}}_{2h}={\mathrm{𝚘𝚙𝚝}}_2$. The quantities ${\mathrm{𝚘𝚙𝚝}}_{3t}$ and ${\mathrm{𝚘𝚙𝚝}}_{3h}$ are defined analogously. Let ${\mathrm{𝚘𝚙𝚝}}_{Lt}:=p(\text{OPT}\cap S)$ and ${\mathrm{𝚘𝚙𝚝}}_{Lh}:=p(\text{OPT}\cap (L\setminus S))$ so that ${\mathrm{𝚘𝚙𝚝}}_{Lt}+{\mathrm{𝚘𝚙𝚝}}_{Lh}={\mathrm{𝚘𝚙𝚝}}_L$. The following theorem repacks items from $I_1\cup S_2\cup S_3\cup S$.

In the previous subsection, we repacked items from $S_2,S_3$ or $S$ together with items in $I_1$. Now we consider items in $(I_2\setminus S_2)\cup (I_3\setminus S_3)\cup (L\setminus S)$ in OPT. As all these items have heights of more than 1/2, they can not be stacked on top of each other. So, we can ignore their heights, and effectively obtain a 2D Knapsack instance. Now we use a container-based algorithm for 2DK from [22] to obtain a container packing of these items.

Equipped with all the lower bounds of the preceding subsections, we establish Lemma 8 by an intricate case analysis depending on the volumes of various sets of items in the optimal packing. Since $v_1,v_2,v_3$ sum up to at most the volume of the knapsack which is 1, at least one among them must not exceed $1/3$. If at most one of them exceeds $1/3$, we show a stronger bound of $\left(\frac{9}{2}+\epsilon \right)$ on the approximation ratio. Otherwise, we assume w.l.o.g. that $v_1\le 1/3$ and $v_2,v_3>1/3$. We further divide into subcases depending on the values of $v_{2s}$ and $v_{3s}$. It turns out that the worst bound on ${\mathrm{𝚘𝚙𝚝}}_{\mathrm{gs}}$ occurs when $v_{2s},v_{3s}$ both exceed $1/3$ and $v_1\le 1/6$. However for this case, Theorem 22 and Theorem 23 give us highly profitable packings, and we achieve an approximation ratio of $\left(\frac{139}{29}+\epsilon \right)$. The details of the analysis are deferred to the full version [16].

When the items can be rotated by 90 degrees around any axis, we show the existence of improved container packing. Specifically, we introduce a new type of container called $𝖫$-Container and obtain improved guarantees based on the packed volume.