defined by $g:=c\times\left[0,h\right]$ or we can pack a subset
$\mathcal{I}^{\prime}\subseteq\mathcal{I}$ of the items leaving free space
inside of this hypercuboid of volume

$\displaystyle\operatorname{VOL}_{d-1}\left(c\right)h-\operatorname{VOL}_{d}\left(\mathcal{I}^{\prime}\right)$
$\displaystyle=\operatorname{VOL}_{d}\left(g\right)-\operatorname{VOL}_{d}\left(\mathcal{I}^{\prime}\right)$
$\displaystyle\leq\rho_{\eta}\frac{\operatorname{SURF}_{d}\left(g\right)}{2}$
$\displaystyle=\rho_{\eta}\left(\frac{\operatorname{SURF}_{d-1}\left(c\right)}{2}h+\operatorname{VOL}_{d-1}\left(c\right)\right).$

We may restate this inequality as

$\displaystyle\left(\operatorname{VOL}_{d-1}\left(c\right)-\rho_{\eta}\frac{\operatorname{SURF}_{d-1}\left(c\right)}{2}\right)h\leq\operatorname{VOL}_{d}\left(\mathcal{I}^{\prime}\right)+\rho_{\eta}\operatorname{VOL}_{d-1}\left(c\right),$

and that is equivalent to

$\displaystyle\operatorname{VOL}_{d}\left(\mathcal{I}\right)+\rho_{\eta}\operatorname{VOL}_{d-1}\left(c\right)\leq\operatorname{VOL}_{d}\left(\mathcal{I}^{\prime}\right)+\rho_{\eta}\operatorname{VOL}_{d-1}\left(c\right).$

This finally yields
$\operatorname{VOL}_{d}\left(\mathcal{I}\right)\leq\operatorname{VOL}_{d}\left(\mathcal{I}^{\prime}\right)$
by using the definition of $h$ and since $\mathcal{I}^{\prime}$ is a subset of
$\mathcal{I}$, we also have
$\operatorname{VOL}_{d}\left(\mathcal{I}\right)\geq\operatorname{VOL}_{d}\left(\mathcal{I}^{\prime}\right)$
and thus all items are packed.

Next, we want to ensure that we can use the packing method described in Lemma
C.9, meaning for each item there is a strip that is large enough to pack the
item into. To do this, we temporarily pack a $(d-k)$ dimensional cube of side
length $\hat{s}$ on $A$ (see Figure 15(a)) and take the set of all intersected
hypercuboids $A_{\text{merged}}\subseteq A$ (see Figure 15(b)). Those
hypercuboids form a larger hypercuboid with side lengths at least $\hat{s}$ in
all $(d-k)$ dimensions.

This is because $A$ is assumed to be a grid. If we assume, that the grid
boundaries are named $g_{i,j}$ for $i\in[d]$ and some values of $j$, then we
find for each dimension $i$ a maximal index $j_{i,-}$ and a minimal index
$j_{i,+}>j_{i,-}$ such that $g_{i,j_{i,-}}$ is smaller than the lowest point
of the packed large item in the $i^{\mathrm{th}}$ dimension and
$g_{i,j_{i,+}}$ is larger than the highest point of the packed large item in
the $i^{\mathrm{th}}$ dimension because the item is packed inside of the grid.
Furthermore the cells
$\Set{\prod_{i=1}^{d}\left[g_{i,j_{i}},g_{i,j_{i}+1}\right]}{j_{i,-}\leq
j_{i}<j_{i,+}\text{ for all }i\in[d]}$ are exactly the cells of $A$ that are
intersected by the packed item. Those cells have to be part of the grid $A$
because otherwise the large item would not be packed into the grid. Combining
those cells creates the hypercuboid
$\prod_{i=1}^{d}\left[g_{i,j_{i,-}},g_{i,j_{i,+}}\right]$

Next, we round the side lengths of each other hypercuboid in $A\backslash
A_{\text{merged}}$ down to the next multiple of
$\hat{s}\left(\mathcal{M}\right)$ and we round the side lengths of the new
hypercuboid $\bigcup_{a\in A_{\text{merged}}}a$ down to the next multiple of
$\hat{s}\left(\mathcal{M}\right)$ to create rounded instances for the
hypercuboids in $A_{\text{merged}}$. This creates a rounded set $A^{\prime}$
of hypercuboids where $A_{\text{merged}}^{\prime}\subseteq A^{\prime}$ are the
rounded instances from the hypercuboids in $A_{\text{merged}}$ (see Figure
15(c)). Note that each hypercuboid in $A^{\prime}$ is formed from a unique
hypercuboid in $A$ by reducing the size in each dimension by at most
$\hat{s}\left(\mathcal{M}\right)$, this is also true for the hypercuboids in
$A_{\text{merged}}^{\prime}$. This allows us to use similar dependencies
between the rounded and non-rounded instances concerning volume and surface,
as we used for the gaps in Section C.3. As a last step, we replace each
$\left(d-k\right)$-dimensional hypercuboid $a$ inside of $A$ or $A^{\prime}$
by its $\left(d-1\right)$-dimensional extension
$a\times\prod_{j=1}^{k-1}[0,b_{j}]$ and define
$A^{\prime\prime}:=A^{\prime}\backslash
A_{\text{merged}}^{\prime}\cup\Set{\bigcup_{a\in
A_{\text{merged}}^{\prime}}a}$ by merging the hypercuboids in
$A_{\text{merged}}^{\prime}$ to a larger hypercuboid as previously announced
(see Figure 15(d)). Now we know that there is at least one base for a strip,
where we can pack any of the medium and small items in.

(a) The grid of $A$ with the largest item (blue) packed into it

(b) The set $A_{\text{merged}}$ is marked in red

(c) The set $A^{\prime}$ is marked as yellow

(d) The set $A^{\prime\prime}$ is marked as yellow

Figure 15: Transforming the grid $A$ to make it suitable for packing the small
and medium items.

######  Lemma C.11.

There exists a hypercuboid $c\in A^{\prime\prime}$, such that
$2\operatorname{VOL}_{d-1}\left(c\right)>\rho_{\eta}\operatorname{SURF}_{d-1}\left(c\right)$.

######  Proof C.12.

Let $c=\left(\bigcup_{a\in A_{\text{merged}}^{\prime}}a\right)$ be the
hypercuboid we got through merging. Let $c_{1},\dots,c_{d-1}$ be the side
lengths of this hypercuboid. Because of the creation and rounding process,
each of those lengths is at least $\hat{s}-\rho_{\eta}$. We have
$\operatorname{VOL}_{d-1}\left(c\right)=\prod_{j=1}^{d-1}c_{j}$. So

$\displaystyle\operatorname{SURF}_{d-1}\left(c\right)=2\operatorname{VOL}_{d-1}\left(c\right)\sum_{j=1}^{d-1}\frac{1}{c_{j}}.$

Thus, we only have to show that $1>\rho_{\eta}\sum_{j=1}^{d-1}1/c_{j}$. It
holds that

$\displaystyle\sum_{j=1}^{d-1}\frac{\rho_{\eta}}{c_{j}}<\sum_{j=1}^{d-1}\frac{\rho_{\eta}}{\hat{s}-\rho_{\eta}}=\sum_{j=1}^{d-1}\frac{1}{\hat{s}/\rho_{\eta}-1}\leq\sum_{j=1}^{d-1}\frac{1}{\hat{s}/\rho_{1}-1}<\sum_{j=1}^{d-1}\frac{1}{d-1}=\frac{d-1}{d-1}=1.$

Now we mark each hypercuboid $c\in A^{\prime\prime}$ for which
$2\operatorname{VOL}_{d-1}\left(c\right)>\rho_{\eta}\operatorname{SURF}_{d-1}\left(c\right)$
holds, knowing that there is at least one, and set it as the base of a strip.
For each base $a\in A^{\prime\prime}$ we assign a subset
$\mathcal{I}_{\text{top},a}$ of the remaining small and medium items and set
its height $h_{\text{top},a}$ according to Lemma C.9. That is, we initialize
$h_{\text{top},a}$ as

$\displaystyle
h_{\text{top},a}=\frac{\rho_{\eta}\operatorname{VOL}_{d-1}\left(c\right)}{\operatorname{VOL}_{d-1}\left(c\right)-\rho_{\eta}\operatorname{SURF}_{d-1}\left(c\right)/2}$

Initially all sets $\mathcal{I}_{\text{top},a}$ are empty. Note that this
still leads to a nonzero initial height for each strip. For each item $x$ that
needs to be assigned, we assign it to a marked base $a\in A^{\prime\prime}$
for which the new height
$h_{\mathrm{top},a}^{\prime}=h_{\mathrm{top},a}+\operatorname{VOL}_{d}\left(x\right)/\left(\operatorname{VOL}_{d-1}\left(c\right)-\rho_{\eta}\operatorname{SURF}_{d-1}\left(c\right)/2\right)$
would be minimal to ensure that those heights stay balanced.

After all items are assigned, we define $h_{\mathrm{top}}$ to be the maximal
height of any strip where we packed an item in and define
$\operatorname{ext}_{\mathrm{top}}$ as the extension of a
$\left(d-1\right)$-dimensional hypercuboid $a$ to the $d$-dimensional
hypercuboid $a\times\left[0,h_{\mathrm{top}}\right]$ of height
$h_{\mathrm{top}}$. We pack $\mathcal{I}_{top,a}$ into
$\operatorname{ext}_{\mathrm{top}}\left(a\right)$ using NFDH for all $a\in
A^{\prime\prime}$ and create this way a new layer $L_{\mathrm{top}}$ of height
$h_{\mathrm{top}}$. Now we can analyze the free volume of each individual box
$\operatorname{ext}_{\mathrm{top}}\left(a\right)$.

######  Lemma C.13.

For all $a\in A^{\prime\prime}$ the free volume inside of the box
$\operatorname{ext}_{\mathrm{top}}\left(a\right)$ is at most

$\displaystyle\operatorname{FVOL}_{d}\left(\operatorname{ext}_{\mathrm{top}}\left(a\right)\right)\leq\rho_{\eta}\frac{\operatorname{SURF}_{d}\left(\operatorname{ext}_{\mathrm{top}}\left(a\right)\right)}{2}+\rho_{\eta}^{d}$

######  Proof C.14.

For the unmarked hypercuboids $a\in A^{\prime\prime}$ the statement is
trivial, as they have
$\operatorname{VOL}_{d-1}\left(a\right)\leq\rho_{\eta}\frac{\operatorname{SURF}_{d-1}\left(a\right)}{2}$
by definition.

Therefore, let $a\in A^{\prime\prime}$ be marked. In this case the strip was
packed using the method explained above. Thus, we know that it is packed to a
large height. More precisely, we know through our balancing method, that
adding an item with side length $\rho_{\eta}$ (which is the upper bound for
the side length of a medium item) would increase the height assigned to that
strip through Lemma C.9 to a larger value than $h_{\mathrm{top}}$.

$\displaystyle h_{\mathrm{top}}$ $\displaystyle\leq
h_{\mathrm{top},a}+\frac{\rho_{\eta}^{d}}{\operatorname{VOL}_{d-1}\left(a\right)-\rho_{\eta}\operatorname{SURF}_{d-1}\left(a\right)/2}$
$\displaystyle=\frac{\operatorname{VOL}_{d}\left(\mathcal{I}_{\mathrm{top},a}\right)+\rho_{\eta}\operatorname{VOL}_{d-1}\left(a\right)+\rho_{\eta}^{d}}{\operatorname{VOL}_{d-1}\left(a\right)-\rho_{\eta}\operatorname{SURF}_{d-1}\left(a\right)/2}$
(by definition of $h_{\mathrm{top},a}$)

Hence, we obtain that

$\displaystyle\operatorname{VOL}_{d-1}\left(a\right)h_{\mathrm{top}}-\rho_{\eta}\frac{\operatorname{SURF}_{d-1}\left(a\right)}{2}h_{\mathrm{top}}\leq\operatorname{VOL}_{d}\left(\mathcal{I}_{\mathrm{top},a}\right)+\rho_{\eta}\operatorname{VOL}_{d-1}\left(a\right)+\rho_{\eta}^{d}$
$\displaystyle\Longleftrightarrow\operatorname{FVOL}_{d}\left(\operatorname{ext}_{\mathrm{top}}\left(a\right)\right)\leq\rho_{\eta}\left(\frac{\operatorname{SURF}_{d-1}\left(a\right)}{2}h_{\mathrm{top}}+\operatorname{VOL}_{d-1}\left(a\right)\right)+\rho_{\eta}^{d}$

By unfolding the definition for the surface we get

$\displaystyle\frac{\operatorname{SURF}_{d}\left(\operatorname{ext}_{\mathrm{top}}\left(a\right)\right)}{2}=\frac{\operatorname{SURF}_{d-1}\left(a\right)}{2}h_{\mathrm{top}}+\operatorname{VOL}_{d-1}\left(a\right).$

This concludes the proof.

Now we can consider the free volume inside of the whole layer.

######  Lemma C.15.

The free volume in layer $L_{\mathrm{top}}$ is at most

$\displaystyle\operatorname{FVOL}_{d}\left(L_{\mathrm{top}}\right)\leq\frac{3}{2}\varepsilon
h_{\mathrm{top}}\operatorname{VOL}_{k-1}\left(B\right)+\frac{\varepsilon}{d-1}\operatorname{VOL}_{k-1}\left(B\right)\hat{s}.$

######  Proof C.16.

We can make a proof similar to the one for Lemma C.7. The layer
$L_{\mathrm{top}}$ can be split into the hypercuboids
$\operatorname{ext}_{\mathrm{top}}\left(a\right)$ for $a\in A$. We start by
relating the hypercuboids in $A$ from our splitting to the volume of the
hypercuboids in $A^{\prime\prime}$ which we used for packing. For the
cardinalities we know
$\left|A^{\prime\prime}\right|\leq\left|A^{\prime}\right|=\left|A\right|\leq
N$. Also, note that since $A^{\prime\prime}$ is obtained from $A^{\prime}$ by
merging a few hypercuboids, $\sum_{a\in
A^{\prime\prime}}\operatorname{VOL}_{d}\left(\operatorname{ext}_{\mathrm{top}}\left(a\right)\right)=\sum_{a\in
A^{\prime}}\operatorname{VOL}_{d}\left(\operatorname{ext}_{\mathrm{top}}\left(a\right)\right)$.
However, $\sum_{a\in
A^{\prime\prime}}\operatorname{SURF}_{d}\left(\operatorname{ext}_{\mathrm{top}}\left(a\right)\right)\leq\sum_{a\in
A^{\prime}}\operatorname{SURF}_{d}\left(\operatorname{ext}_{\mathrm{top}}\left(a\right)\right)$.

$\displaystyle\sum_{a\in
A}\operatorname{VOL}_{d}\left(\operatorname{ext}_{\mathrm{top}}\left(a\right)\right)$
$\displaystyle\leq$ $\displaystyle\sum_{a\in
A^{\prime}}\left(\operatorname{VOL}_{d}\left(\operatorname{ext}_{\mathrm{top}}\left(a\right)\right)+\rho_{\eta}\left(d-k\right)h_{\mathrm{top}}\left(\alpha\hat{s}\right)^{d-k-1}\operatorname{VOL}_{k-1}\left(B\right)\right)$
(similar to Lemma C.5 but with $\rho_{\eta}$ and
$h_{\mathrm{top}}\operatorname{VOL}_{k-1}\left(B\right)$ instead of
$\rho_{\eta+1}$ and $x_{i}^{*}$) $\displaystyle\leq$ $\displaystyle
N\rho_{\eta}\operatorname{VOL}_{k-1}\left(B\right)\left(d-k\right)h_{\mathrm{top}}\left(\alpha\hat{s}\right)^{d-k-1}+\sum_{a\in
A^{\prime\prime}}\operatorname{VOL}_{d}\left(\operatorname{ext}_{\mathrm{top}}\left(a\right)\right)$

Similar to how we upper-bounded
$\operatorname{SURF}_{d}\left(\operatorname{ext}^{\prime}(g)\right)/2$ in
Lemma C.7, instead of using $x_{i}^{*}$, if we use
$h_{\mathrm{top}}\operatorname{VOL}_{k-1}\left(B\right)$, we obtain

$\displaystyle\frac{\operatorname{SURF}_{d}\left(\operatorname{ext}_{\mathrm{top}}\left(a\right)\right)}{2}\leq\operatorname{VOL}_{k-1}\left(B\right)\left(\left(d-k\right)h_{\mathrm{top}}\left(\alpha\hat{s}\right)^{d-k-1}+\left(\alpha\hat{s}\right)^{d-k}\left(h_{\mathrm{top}}\left(k-1\right)+1\right)\right)$

By applying those two inequalities and Lemma C.13 we can bound the free volume
to:

$\displaystyle\quad\operatorname{FVOL}_{d}\left(L_{\mathrm{top}}\right)$
$\displaystyle=\sum_{a\in
A}\operatorname{VOL}_{d}\left(\operatorname{ext}_{\mathrm{top}}\left(a\right)\right)-\sum_{a\in
A^{\prime\prime}}\operatorname{VOL}_{d}\left(\mathcal{I}_{top,a}\right)$
$\displaystyle\leq
N\rho_{\eta}\operatorname{VOL}_{k-1}\left(B\right)\left(d-k\right)h_{\mathrm{top}}\left(\alpha\hat{s}\right)^{d-k-1}+\sum_{a\in
A^{\prime\prime}}\left(\operatorname{VOL}_{d}\left(\operatorname{ext}_{\mathrm{top}}\left(a\right)\right)-\operatorname{VOL}_{d}\left(\mathcal{I}_{top,a}\right)\right)$
$\displaystyle\leq
N\rho_{\eta}\operatorname{VOL}_{k-1}\left(B\right)\left(d-k\right)h_{\mathrm{top}}\left(\alpha\hat{s}\right)^{d-k-1}+\sum_{a\in
A^{\prime\prime}}\left(\rho_{\eta}\frac{\operatorname{SURF}_{d}\left(\operatorname{ext}_{\mathrm{top}}\left(a\right)\right)}{2}+\rho_{\eta}^{d}\right)$
(Lemma C.13) $\displaystyle\leq
N\rho_{\eta}\operatorname{VOL}_{k-1}\left(B\right)\left(d-k\right)h_{\mathrm{top}}\left(\alpha\hat{s}\right)^{d-k-1}+\sum_{a\in
A^{\prime}}\left(\rho_{\eta}\frac{\operatorname{SURF}_{d}\left(\operatorname{ext}_{\mathrm{top}}\left(a\right)\right)}{2}+\rho_{\eta}^{d}\right)$
$\displaystyle\leq
N\rho_{\eta}\operatorname{VOL}_{k-1}\left(B\right)\left(2\left(d-k\right)h_{\mathrm{top}}\left(\alpha\hat{s}\right)^{d-k-1}+\left(\alpha\hat{s}\right)^{d-k}\left(h_{\mathrm{top}}\left(k-1\right)+1\right)\right)$
$\displaystyle\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad+N\rho_{\eta}^{d}$

Now we can use the fact that $\rho_{\eta}\leq\rho_{1}$ which is
$\varepsilon\hat{s}/\left(2\left(d-1\right)N\left(\alpha\hat{s}\right)^{d-k}\right)$.
We use this to simplify the individual summands of this inequality.

$\displaystyle
N\rho_{\eta}\operatorname{VOL}_{k-1}\left(B\right)2\left(d-k\right)h_{\mathrm{top}}\left(\alpha\hat{s}\right)^{d-k-1}\leq\varepsilon
h_{\mathrm{top}}\operatorname{VOL}_{k-1}\left(B\right)$ $\displaystyle
N\rho_{\eta}\operatorname{VOL}_{k-1}\left(B\right)\left(\alpha\hat{s}\right)^{d-k}h_{\mathrm{top}}\left(k-1\right)\leq\frac{\varepsilon}{2}\frac{k-1}{d-1}\hat{s}h_{\mathrm{top}}\operatorname{VOL}_{k-1}\left(B\right)\leq\frac{\varepsilon}{2}h_{\mathrm{top}}\operatorname{VOL}_{k-1}\left(B\right)$
$\displaystyle
N\rho_{\eta}\operatorname{VOL}_{k-1}\left(B\right)\left(\alpha\hat{s}\right)^{d-k}\leq\frac{\varepsilon}{2\left(d-1\right)}\hat{s}\operatorname{VOL}_{k-1}\left(B\right)$
$\displaystyle
N\rho_{\eta}^{d}\leq\frac{\varepsilon}{2\left(d-1\right)}\frac{1}{\alpha^{d-k}}\frac{\rho_{\eta}^{d-k}}{\hat{s}^{d-k}}\rho_{\eta}^{k-1}\hat{s}\leq\frac{\varepsilon}{2\left(d-1\right)}\hat{s}\operatorname{VOL}_{k-1}\left(B\right)$

This sums up to the inequality

$\displaystyle\operatorname{FVOL}_{d}\left(L_{\mathrm{top}}\right)\leq\frac{3}{2}\varepsilon
h_{\mathrm{top}}\operatorname{VOL}_{k-1}\left(B\right)+\frac{\varepsilon}{d-1}\operatorname{VOL}_{k-1}\left(B\right)\hat{s}.$

Now, that all items are packed, we extend the size of the top layer in the
long dimensions by $\hat{s}$. This way, we gain enough space to also increase
the size of the boxes inside of the top layer in those dimensions, such that
their side lengths are multiples of $\hat{s}\left(\mathcal{M}\right)$ and they
are thus $\mathcal{V}$-Boxes.

###  C.5 Analysis

Now we can analyze the total height $h_{\mathrm{total}}$ of the packing. We
have to distinguish between the case where all of the small items are packed
in the gaps and the case where some of them were packed in the top layer. If
the gaps were all filled with a large volume of small items, we can use volume
arguments to find a bound on the height $h_{\mathrm{total}}$.

######  Lemma C.17.

If not all small items were packed into the gaps of the layers
$L_{1},\dots,L_{N_{\mathrm{configs}}}$, then we have a height of

$\displaystyle
h_{\mathrm{total}}\leq\left(1+5\varepsilon\right)\operatorname{OPT}_{\mathrm{strip}}\left(\mathcal{I},A,B\right)+2\left(N_{\mathrm{configs}}+2\right)\hat{s}.$

######  Proof C.18.

Let
$\operatorname{VOL}_{d-k}\left(P_{i}\right):=\sum_{j=1}^{N_{\mathrm{sizes}}}c_{i,j}\hat{s}\left(\mathcal{G}_{j}\right)^{d-k}$
be the volume of the $\left(d-k\right)$-dimensional packing $P_{i}$ associated
with configuration $i$. By Lemma C.1 we can bound the volume of the large
items:

$\displaystyle\operatorname{VOL}_{d}\left(\mathcal{L}_{\mathrm{up}}\right)$
$\displaystyle=\sum_{j=1}^{N_{\mathrm{sizes}}}\left|\mathcal{G}_{j}\right|\hat{s}\left(\mathcal{G}_{j}\right)^{d}=\sum_{j=1}^{N_{\mathrm{sizes}}}\sum_{i=1}^{N_{\mathrm{configs}}}x_{i}^{*}c_{i,j}\hat{s}\left(\mathcal{G}_{j}\right)^{d-k}=\sum_{i=1}^{N_{\mathrm{configs}}}\operatorname{VOL}_{d-k}\left(P_{i}\right)x_{i}^{*}$
$\displaystyle\operatorname{VOL}_{d}\left(\mathcal{L}\right)$
$\displaystyle\geq\operatorname{VOL}_{d}\left(\mathcal{L}_{\mathrm{up}}\right)-\varepsilon\operatorname{VOL}_{d}\left(\mathcal{L}\right)-\operatorname{VOL}_{k-1}\left(B\right)\hat{s}$
$\displaystyle=\sum_{i=1}^{N_{\mathrm{configs}}}\operatorname{VOL}_{d-k}\left(P_{i}\right)x_{i}^{*}-\varepsilon\operatorname{VOL}_{d}\left(\mathcal{L}\right)-\operatorname{VOL}_{k-1}\left(B\right)\hat{s}.$

We can bound the volume $V_{1}$ of the small items that were packed between
the large items using Lemma C.7:

$\displaystyle V_{1}$
$\displaystyle:=\sum_{i=1}^{N_{\mathrm{configs}}}\left(\operatorname{VOL}_{d}\left(L_{i}\right)-\operatorname{FVOL}_{d}\left(L_{i}\right)-\operatorname{VOL}_{d-k}\left(P_{i}\right)x_{i}^{*}\right)$
$\displaystyle\geq\sum_{i=1}^{N_{\mathrm{configs}}}\left(x_{i}^{*}-\frac{3}{2}\varepsilon
x_{i}^{*}-\frac{\varepsilon}{d-1}\operatorname{VOL}_{k-1}\left(B\right)\hat{s}-\operatorname{VOL}_{d-k}\left(P_{i}\right)x_{i}^{*}\right)$
(using $\operatorname{VOL}_{d}\left(L_{i}\right)=x_{i}^{*}$)
$\displaystyle=\left(1-\frac{3}{2}\varepsilon\right)\left(\sum_{i=1}^{N_{\mathrm{configs}}}h_{i}\right)\operatorname{VOL}_{k-1}\left(B\right)-N_{\mathrm{configs}}\frac{\varepsilon}{d-1}\operatorname{VOL}_{k-1}\left(B\right)\hat{s}-\sum_{i=1}^{N_{\mathrm{configs}}}\operatorname{VOL}_{d-k}\left(P_{i}\right)x_{i}^{*}$
(using $h_{i}=x_{i}^{*}/\operatorname{VOL}_{k-1}\left(B\right)$)
$\displaystyle>\left(1-\frac{3}{2}\varepsilon\right)\left(\sum_{i=1}^{N_{\mathrm{configs}}}h_{i}\right)\operatorname{VOL}_{k-1}\left(B\right)-N_{\mathrm{configs}}\frac{3}{2}\varepsilon\operatorname{VOL}_{k-1}\left(B\right)\hat{s}-\sum_{i=1}^{N_{\mathrm{configs}}}\operatorname{VOL}_{d-k}\left(P_{i}\right)x_{i}^{*}.$

The volume $V_{2}$ of the remaining small and medium items is located in the
top layer and we can bound it using Lemma C.15:

$\displaystyle V_{2}$
$\displaystyle:=\operatorname{VOL}_{d}\left(L_{\mathrm{top}}\right)-\operatorname{FVOL}_{d}\left(L_{\mathrm{top}}\right)$
$\displaystyle\geq
h_{\mathrm{top}}\operatorname{VOL}_{k-1}\left(B\right)-\frac{3}{2}\varepsilon
h_{\mathrm{top}}\operatorname{VOL}_{k-1}\left(B\right)-\frac{\varepsilon}{d-1}\operatorname{VOL}_{k-1}\left(B\right)\hat{s}$
$\displaystyle=\left(1-\frac{3}{2}\varepsilon\right)h_{\mathrm{top}}\operatorname{VOL}_{k-1}\left(B\right)-\frac{\varepsilon}{d-1}\operatorname{VOL}_{k-1}\left(B\right)\hat{s}$
$\displaystyle>\left(1-\frac{3}{2}\varepsilon\right)h_{\mathrm{top}}\operatorname{VOL}_{k-1}\left(B\right)-\frac{3}{2}\varepsilon\operatorname{VOL}_{k-1}\left(B\right)\hat{s}.$

Recall that
$h_{\mathrm{total}}=\sum_{i=1}^{N_{\mathrm{configs}}}\left(h_{i}+\hat{s}\right)+h_{\mathrm{top}}+\hat{s}$.
The bound on the total volume of small and medium items is therefore:

$\displaystyle\quad\operatorname{VOL}_{d}\left(\mathcal{S}\right)+\operatorname{VOL}_{d}\left(\mathcal{M}\right)$
$\displaystyle=V_{1}+V_{2}$
$\displaystyle>\left(1-\frac{3}{2}\varepsilon\right)\left(h_{\mathrm{total}}-\left(N_{\mathrm{configs}}+1\right)\hat{s}\right)\operatorname{VOL}_{k-1}\left(B\right)$
$\displaystyle\quad-\left(N_{\mathrm{configs}}+1\right)\frac{3}{2}\varepsilon\operatorname{VOL}_{k-1}\left(B\right)\hat{s}-\sum_{i=1}^{N_{\mathrm{configs}}}\operatorname{VOL}_{d-k}\left(P_{i}\right)x_{i}^{*}$
$\displaystyle=\left(1-\frac{3}{2}\varepsilon\right)h_{\mathrm{total}}\operatorname{VOL}_{k-1}\left(B\right)-\left(N_{\mathrm{configs}}+1\right)\left(1-\frac{3}{2}\varepsilon\right)\operatorname{VOL}_{k-1}\left(B\right)\hat{s}$
$\displaystyle\quad-\left(N_{\mathrm{configs}}+1\right)\frac{3}{2}\varepsilon\operatorname{VOL}_{k-1}\left(B\right)\hat{s}-\sum_{i=1}^{N_{\mathrm{configs}}}\operatorname{VOL}_{d-k}\left(P_{i}\right)x_{i}^{*}$
$\displaystyle=\left(1-\frac{3}{2}\varepsilon\right)h_{\mathrm{total}}\operatorname{VOL}_{k-1}\left(B\right)-\left(N_{\mathrm{configs}}+1\right)\operatorname{VOL}_{k-1}\left(B\right)\hat{s}-\sum_{i=1}^{N_{\mathrm{configs}}}\operatorname{VOL}_{d-k}\left(P_{i}\right)x_{i}^{*}.$

Thus, we have a bound on the volume of all items:

$\displaystyle\left(1+\varepsilon\right)\operatorname{VOL}_{d}\left(\mathcal{I}\right)$
$\displaystyle=\operatorname{VOL}_{d}\left(\mathcal{L}\right)+\operatorname{VOL}_{d}\left(\mathcal{S}\right)+\operatorname{VOL}_{d}\left(\mathcal{M}\right)+\varepsilon\operatorname{VOL}_{d}\left(\mathcal{I}\right)$
$\displaystyle>\sum_{i=1}^{N_{\mathrm{configs}}}\operatorname{VOL}_{d-k}\left(P_{i}\right)x_{i}^{*}-\varepsilon\operatorname{VOL}_{d}\left(\mathcal{L}\right)-\operatorname{VOL}_{k-1}\left(B\right)\hat{s}$
$\displaystyle\quad+\left(1-\frac{3}{2}\varepsilon\right)h_{\mathrm{total}}\operatorname{VOL}_{k-1}\left(B\right)-\left(N_{\mathrm{configs}}+1\right)\operatorname{VOL}_{k-1}\left(B\right)\hat{s}$
$\displaystyle\quad-\sum_{i=1}^{N_{\mathrm{configs}}}\operatorname{VOL}_{d-k}\left(P_{i}\right)x_{i}^{*}+\varepsilon\operatorname{VOL}_{d}\left(\mathcal{I}\right)$
$\displaystyle\geq\left(1-\frac{3}{2}\varepsilon\right)h_{\mathrm{total}}\operatorname{VOL}_{k-1}\left(B\right)-\left(N_{\mathrm{configs}}+2\right)\operatorname{VOL}_{k-1}\left(B\right)\hat{s}.$

This gives us the claimed bound on the height. It holds that

$\displaystyle h_{\mathrm{total}}$
$\displaystyle\leq\frac{1+\varepsilon}{1-\frac{3}{2}\varepsilon}\frac{\operatorname{VOL}_{d}\left(\mathcal{I}\right)}{\operatorname{VOL}_{k-1}\left(B\right)}+\frac{1}{1-\frac{3}{2}\varepsilon}\left(N_{\mathrm{configs}}+2\right)\hat{s}$
$\displaystyle\leq\left(1+5\varepsilon\right)\operatorname{OPT}_{\mathrm{strip}}\left(\mathcal{I},A,B\right)+2\left(N_{\mathrm{configs}}+2\right)\hat{s}.$

For the last step we use
$2\left(1+\varepsilon\right)/\left(2-3\varepsilon\right)\leq 1+5\varepsilon$
for $\varepsilon\leq 1/3$ and the fact that

$\displaystyle\operatorname{OPT}_{\mathrm{strip}}\left(\mathcal{I},A,B\right)\geq\frac{\operatorname{VOL}_{d}\left(\mathcal{I}\right)}{\operatorname{VOL}_{d-k}\left(A\right)\operatorname{VOL}_{k-1}\left(B\right)}=\frac{\operatorname{VOL}_{d}\left(\mathcal{I}\right)}{\operatorname{VOL}_{k-1}\left(B\right)}.$

If all small items were packed in the gaps, the top layer only contains items
of medium size. By choice of $\eta$, we know that the medium items have a
small total volume. Thus we can argue that the height of $h_{\mathrm{top}}$ of
the top layer is small, which also gives us a good bound on
$h_{\mathrm{total}}$.

######  Lemma C.19.

If all small items were packed into the gaps of the layers
$L_{1},\dots,L_{N_{\mathrm{configs}}}$, then we have a height of

$\displaystyle
h_{\mathrm{total}}\leq\left(1+\left(2^{k-1}+2\right)\varepsilon\right)\operatorname{OPT}_{\mathrm{strip}}\left(\mathcal{I},A,B\right)+\left(N_{\mathrm{configs}}+3\right)\hat{s}.$

######  Proof C.20.

By the choice of $\mathcal{M}$ and Lemma C.15 we have

$\displaystyle\varepsilon\operatorname{VOL}_{d}\left(\mathcal{I}\right)$
$\displaystyle\geq\operatorname{VOL}_{d}\left(\mathcal{M}\right)=\operatorname{VOL}_{d}\left(L_{\mathrm{top}}\right)-\operatorname{FVOL}_{d}\left(L_{\mathrm{top}}\right)$
$\displaystyle\geq
h_{\mathrm{top}}\operatorname{VOL}_{k-1}\left(B\right)-\frac{3}{2}\varepsilon
h_{\mathrm{top}}\operatorname{VOL}_{k-1}\left(B\right)-\frac{\varepsilon}{d-1}\operatorname{VOL}_{k-1}\left(B\right)\hat{s}.$

This gives us a bound on the height of the top layer:

$\displaystyle h_{\mathrm{top}}$
$\displaystyle\leq\frac{\varepsilon}{1-\frac{3}{2}\varepsilon}\frac{\operatorname{VOL}_{d}\left(\mathcal{I}\right)}{\operatorname{VOL}_{k-1}\left(B\right)}+\frac{\varepsilon}{1-\frac{3}{2}\varepsilon}\frac{1}{d-1}\hat{s}$
$\displaystyle\leq
2\varepsilon\operatorname{OPT}_{\mathrm{strip}}\left(\mathcal{I},A,B\right)+\frac{2}{3\left(d-1\right)}\hat{s}$
$\displaystyle<2\varepsilon\operatorname{OPT}_{\mathrm{strip}}\left(\mathcal{I},A,B\right)+\hat{s}.$

By applying this, we can prove the claimed bound on the total height:

$\displaystyle h_{\mathrm{total}}$
$\displaystyle=\sum_{i=1}^{N_{\mathrm{configs}}}h_{i}+h_{\mathrm{top}}+\left(N_{\mathrm{configs}}+1\right)\hat{s}$
$\displaystyle\leq\operatorname{OPT}_{\mathrm{strip}}\left(\mathcal{L}_{\mathrm{up}},A,B\right)+2\varepsilon\operatorname{OPT}_{\mathrm{strip}}\left(\mathcal{I},A,B\right)+\left(N_{\mathrm{configs}}+2\right)\hat{s}$
(using Lemma C.3)
$\displaystyle\leq\left(1+\left(2+2^{k-1}\right)\varepsilon\right)\operatorname{OPT}_{\mathrm{strip}}\left(\mathcal{I},A,B\right)+\left(N_{\mathrm{configs}}+3\right)\hat{s}$
(using Lemma C.1 and $\mathcal{L}\subseteq\mathcal{I}$)

The only part missing for the proof of Theorem 3.8 is a constant bound on
$N_{\mathrm{configs}}$.

######  Lemma C.21.

The numbers $\rho_{\eta}$, $N_{\mathrm{sizes}}$ and $N_{\mathrm{configs}}$ can
be bounded by constants that are only dependent on $d$, $k$, $\alpha$, $N$ and
$\varepsilon$.

######  Proof C.22.

In the following we will define new constants formally as functions over the
constants $d$, $k$, $\alpha$, $N$ and $\varepsilon$ received from the problem
definition to show their dependencies. As those values never change throughout
this proof, we will however skip those arguments when using the newly defined
constants to gain clearer formulas. First of all we can bound $\rho_{1}$ in
the following way:

$\displaystyle\rho_{1}$
$\displaystyle=\frac{\varepsilon\hat{s}}{2\left(d-1\right)N\left(\alpha\hat{s}\right)^{d-k}}$
$\displaystyle=\frac{\varepsilon}{2\left(d-1\right)N\alpha^{d-k}\hat{s}^{d-k-1}}$
$\displaystyle\geq\frac{\varepsilon}{2\left(d-1\right)N\alpha^{d-k}}$ (using
$\hat{s}\leq 1$)
$\displaystyle=:C_{\mathrm{\rho,1}}\left(d,k,\alpha,N,\varepsilon\right).$

Now we can bound $\rho_{i}\geq C_{\mathrm{\rho,i}}$ with

$\displaystyle
C_{\mathrm{\rho,i}}\left(d,k,\alpha,N,\varepsilon\right):=\frac{C_{\mathrm{\rho,1}}^{i\left(d-k\right)^{2i-2}}}{2^{\left(i-1\right)\left(d-k\right)^{2i-3}}}.$

We prove it by induction. For $i=1$ the new definition of
$C_{\mathrm{\rho,1}}$ is consistent with the old one and thus the bound is
already shown above. For $i+1$ we can prove the bound with

$\displaystyle\rho_{i+1}$
$\displaystyle=\rho_{1}\frac{\rho_{i}^{\left(d-k\right)^{2}}}{2^{d-k}}$
$\displaystyle\geq\frac{C_{\mathrm{\rho,1}}}{2^{d-k}}\left(\frac{C_{\mathrm{\rho,1}}^{i\left(d-k\right)^{2i-2}}}{2^{\left(i-1\right)\left(d-k\right)^{2i-3}}}\right)^{\left(d-k\right)^{2}}$
$\displaystyle=\frac{C_{\mathrm{\rho,1}}}{2^{d-k}}\frac{C_{\mathrm{\rho,1}}^{i\left(d-k\right)^{2i}}}{2^{\left(i-1\right)\left(d-k\right)^{2i-1}}}$
$\displaystyle\geq\frac{C_{\mathrm{\rho,1}}^{\left(i+1\right)\left(d-k\right)^{2i}}}{2^{i\left(d-k\right)^{2i-1}}}$
$\displaystyle=C_{\mathrm{\rho,i+1}}.$

Using $\eta\leq\left\lceil 1/\varepsilon\right\rceil$ we get $\rho_{\eta}\geq
C_{\mathrm{\rho,\left\lceil
1/\varepsilon\right\rceil}}=:C_{\mathrm{\rho}}\left(d,k,\alpha,N,\varepsilon\right)$.
With this bound we can bound the number of sizes to which we round the large
items to

$\displaystyle
N_{\mathrm{sizes}}=\left\lceil\frac{1}{\varepsilon\rho_{\eta}^{d}}\right\rceil\leq\frac{1}{\varepsilon
C_{\mathrm{\rho}}^{d}}+1=:C_{\mathrm{sizes}}\left(d,k,\alpha,N,\varepsilon\right).$

The number of configurations can now be bounded by

$\displaystyle
N_{\mathrm{configs}}\leq\left(\frac{1}{\rho_{\eta}^{d-k}}+1\right)^{N_{\mathrm{sizes}}}\leq\left(\frac{1}{C_{\mathrm{\rho}}^{d-k}}+1\right)^{C_{\mathrm{sizes}}}=:C_{\mathrm{configs}}\left(d,k,\alpha,N,\varepsilon\right).$

Note, that we have the following property which is important in Section 3.

######  Lemma C.23.

$C_{\mathrm{configs}}>1/C_{\mathrm{\rho,1}}>N\alpha^{d-k}\geq\alpha$.

######  Proof C.24.

$\displaystyle C_{\mathrm{configs}}$
$\displaystyle=\left(\frac{1}{C_{\mathrm{\rho}}^{d-k}}+1\right)^{C_{\mathrm{sizes}}}$
(From definition of $C_{\mathrm{configs}}$)
$\displaystyle\geq{1}/{C_{\mathrm{\rho}}}$ (As $C_{\mathrm{\rho}}\leq
1,C_{\mathrm{sizes}}\geq 1$) $\displaystyle\geq 1/C_{\mathrm{\rho,1}}$ (As
$C_{\mathrm{\rho,1}}\geq C_{\mathrm{\rho}}$)
$\displaystyle=2(d-1)N\alpha^{d-k}/\varepsilon$ (From definition of
$C_{\mathrm{\rho,1}}$) $\displaystyle>N\alpha^{d-k}$ (As $d\geq
2,\varepsilon<1$) $\displaystyle\geq\alpha$ (As $N\geq 1,\alpha\geq 1$)

######  Lemma C.25.

The strip packing algorithm of Appendix C packs all items in
$\mathcal{N}$-Boxes and $\mathcal{V}$-Boxes. The number of $\mathcal{N}$-Boxes
is bounded by $C_{\mathrm{configs}}/C_{\rho}^{d-k}$ and the number of
$\mathcal{V}$-Boxes is bounded by
$C_{\mathrm{configs}}N2^{d-k}/C_{\mathrm{\rho}}^{\left(d-k\right)^{2}}+N$.

######  Proof C.26.

Note that the strip packing algorithm creates $\mathcal{N}$-Boxes only at the
end of Section C.2. In this step, one $\mathcal{N}$-Box is created for each
large item in each configuration. As mentioned before, the volume of $A$ is
$1$ and each large item has a side length of at least $\rho_{\eta}$. Thus,
there are at most $1/C_{\mathrm{\rho}}^{d-k}$ large items per configuration
and there are at most $C_{\mathrm{configs}}$ configurations. This results in
an upper bound of $C_{\mathrm{configs}}/C_{\rho}^{d-k}$ for the number of
$\mathcal{N}$-Boxes.

$\mathcal{V}$-Boxes are created in two steps of the algorithm. The first step
is stated in Section C.3 where we create a $\mathcal{V}$-Box for each gap in
each layer that was created for the large items. There is one layer for each
configuration and in the beginning of Section C.3, the number of gaps per
layer is bounded by $2^{d-k}/\rho_{\eta}^{\left(d-k\right)^{2}}$. Thus, there
are at most
$C_{\mathrm{configs}}N\left(2^{d-k}/C_{\mathrm{\rho}}^{\left(d-k\right)^{2}}\right)$
$\mathcal{V}$-Boxes created in this step. The second step where
$\mathcal{V}$-Boxes are created is in Section C.4 where we place the remaining
small and medium items in an additional layer. There, the number of
$\mathcal{V}$-Boxes is bounded by the number of cells in $A$ which is bounded
by $N$. This concludes our proof.