A 13/6-Approximation for Strip Packing via the Bottom-Left Algorithm

By definition of $H_i$, all rectangles placed prior to $r_i$ have their bottom face below $H_i$. Hence, if an unoccupied gap in $\mathrm{\ell }$ has size at least $w_{r_i}$ when $r_i$ is placed, then this contradicts the BL algorithm, because the gap is a lower position where we can place $r_i$. $◀$

We consider the iteration of the BL algorithm in which rectangle $r_i$ is placed. By Lemma 2, in this iteration, each occupied part of $\mathrm{\ell }$ is at least as wide as each unoccupied gap, because the rectangles intersecting $\mathrm{\ell }$ have width at least $w_{r_i}$ by assumption. If the line contains $k\ge 1$ occupied parts in this iteration then it can contain at most $k+1$ unoccupied parts. Thus, at least a $k/(2k+1)$ fraction of the line is occupied. If the leftmost or rightmost part of the line is occupied by a rectangle, then there are at most as many unoccupied parts as there are occupied parts. Hence in this case at least a $k/(2k)=1/2$ fraction of the line is occupied. In later iterations of the BL algorithm more rectangles may be placed that intersect the line. However, this will only increase the fraction of the line that is occupied by rectangles.

It remains to show that the statement holds for any horizontal line in the region $H_i$. The $k$ rectangles that intersect $\mathrm{\ell }$ have their bottom face below $H_i$ by definition of the horizontal strip partition. And the $k$ rectangles have their top faces above $H_i$, as else $r_i$ can be placed lower on top of such a rectangle, since the $k$ rectangles each have width at least $w_{r_i}$. Hence, any proper horizontal line in $H_i$ intersects the $k$ rectangles that intersect $\mathrm{\ell }$, and thus each such line satisfies the statements as desired. $◀$

Observe that when rectangles are ordered by decreasing width, then every region satisfies the condition in Lemma 3. Additionally, in this case, Baker et al. [1] show that the leftmost part of a proper horizontal line is always occupied by a rectangle.

For $r\in 𝒬\cup 𝒲$ we have $w_r+{\sum }_{f\in {ℱ}_{\ge h_r}}{w}_f>W$ by the definition of $ℱ$. Hence there are at least two rectangles in ${ℱ}_{\ge h_r}\cup \{r\}$ that cannot be next to each other in the optimal packing. As each such rectangle has height at least $h_r$, it follows that $2h_r$ is a lower bound on the height $h_{\text{OPT}}$ of an optimum packing. $◀$

For a Strip Packing instance $ℐ$, we order the rectangles based on the $ℱ𝒬𝒲$-partition as follows: first sort the rectangles from $ℱ$ by decreasing height, next order the rectangles from $𝒬$ by decreasing width, and finally take any ordering of $𝒲$. We break ties arbitrarily. We denote the BL packing obtained from this $ℱ𝒬𝒲$-ordering by $\text{BL}({ℐ}_{ℱ𝒬𝒲})$. Figure 1 illustrates an example.

All rectangles from $ℱ$ are placed on the bottom of the strip and have height at most $h_{\text{max}}$. If there are no rectangles in $𝒬$, or if the highest top face in $𝒬$ is below $h_{\text{max}}$, then in the worst case all rectangles from $𝒲$ are stacked on top of each other at height $h_{\text{max}}$. Thus it holds that $h_{\text{BL}}\le h_{\text{max}}+{\sum }_{r\in 𝒲}{h}_r$. Now both $h_{\max }$ and ${\sum }_{r\in 𝒲}{h}_r$ are lower bounds on the height of an optimal packing, which implies $h_{\text{BL}}\le 2h_{\text{OPT}}$. $◀$

Thus, from now on, we may assume that $𝒬\ne \mathrm{\varnothing }$ and that there exists some rectangle $r\in 𝒬$ for which it holds that $y_r+h_r>h_{\text{max}}$. The next result explains why the rectangles from $𝒲$ are placed after rather than before $𝒬$.

The rectangles in $ℱ$ are placed next to each other at the bottom of the strip and are ordered from left to right by decreasing height. The first rectangle $r_{a+1}$ from $𝒬$ is placed according to the BL algorithm on top of this first row at height $y_{r_{a+1}}$. Let $f$ be the rightmost rectangle in $ℱ$ whose top face is at height $y_{r_{a+1}}$. Such a rectangle always exists as $r_{a+1}$ must have a bottom supporter (cf. Section 2.1). As $r_{a+1}$ cannot be placed at a lower position, it follows that the gap between the right side of $f$ and the right strip boundary is strictly less than $w_{r_{a+1}}$, which is less than $\frac{1}{2}W$ by definition of $𝒬$. Therefore, each horizontal line in $H_{a+1}$ is at least half occupied. $◀$

We continue by analyzing the regions corresponding to rectangles from $𝒲$.

Each region $H_i$ contains at least one rectangle from $𝒲$. Thus, a proper horizontal line in $H_i$ intersects a rectangle with width at least $W/2$. $◀$

Next, we consider the region $H_{a+b+1}$ between the highest bottom face of a rectangle from $𝒬$ and the bottom face of the first rectangle that is placed from $𝒲$. Define the top rectangle of $𝒬$ as the rectangle $r_T$ in $𝒬$ whose top face is placed highest by the BL algorithm; and in case of ties we let $r_T$ be one with highest bottom face (in the example shown in Figure 1 the rectangle $r_{11}$ is the rectangle $r_T$). Then any proper horizontal line in $H_{a+b+1}$ intersects $r_T$. The rectangle $r_T$ might be the only rectangle that such a line intersects, and $w_{r_T}$ can be small, hence an arbitrarily small fraction of the line might be occupied by rectangles. Thus, the region $H_{a+b+1}$ can be very sparsely occupied. However, for a superset of $H_{a+b+1}$ the following lemma shows that we get again an at least half occupied space. Note that we have $H_{a+b+1}\subseteq [0,W]\times [y_{r_T},y_{r_T}+h_{r_T}]$.

It holds that $y_{r_T}\ge h_{r_T}$ by construction of $ℱ$. Moreover, the total width of the rectangles in $\{r_T\}\cup {ℱ}_{\ge h_{r_T}}$ exceeds the width of the strip. Thus the BL algorithm occupies inside $H^{\prime }$ an area of at least $W\cdot h_{r_T}$ by rectangles. As $H^{\prime }$ has area $2W\cdot h_{r_T}$ it is at least half occupied. $◀$

It remains to study the regions $H_i$ for $i\in \{a+2,\mathrm{\dots },a+b\}$. For this, we define the left rectangle of $𝒬$ to be the first rectangle $r_L$ from $𝒬$ that touches the left strip boundary (in the example shown in Figure 1 the rectangle $r_8$ is the rectangle $r_L$). If no rectangle in $𝒬$ touches the left strip boundary, then we set $r_L:=r_T$. In Section 3.3 we will develop a technique to prove that the union $H_{a+2}\cup \mathrm{\cdots }\cup H_L$ is almost half occupied by rectangles. But first, we consider the regions $H_{L+1},\mathrm{\dots },H_{a+b}$. Since the rectangles in $𝒬$ are ordered by decreasing width we can apply Lemma 3.

If $r_L=r_T$, then $H_i\subseteq H^{\prime }$. We thus may assume that $r_L\ne r_T$. A proper horizontal line $\mathrm{\ell }$ in $H_i$ is above the bottom face of $r_L$. Therefore, prior to placing $r_i$, the line $\mathrm{\ell }$ only intersects rectangles from $𝒬$ and these rectangles have width at least $w_{r_i}$. Additionally, we will show that the leftmost part of $\mathrm{\ell }$ is occupied by a rectangle. Then Lemma 3 implies that $\mathrm{\ell }$ is at least half occupied.

This argument is based on [1]. Let $r^{\prime }$ be the highest rectangle placed before $r_i$ that touches the left strip boundary. Such $r^{\prime }$ exists and is part of $𝒬$, because $r_L\in 𝒬$ touches the left strip boundary and no rectangle from $ℱ$ is above $r_L$. Since $r^{\prime }$ is placed before $r_i$, it follows that the bottom face of $r^{\prime }$ must be placed below the proper line $\mathrm{\ell }$ by definition of the horizontal strip partition. If $r^{\prime }$ intersects $\mathrm{\ell }$, then the first part of $\mathrm{\ell }$ is occupied by a rectangle. Otherwise, we show that there is no rectangle placed before $r_i$ that is above $r^{\prime }$ and whose left face is strictly to the left of the right face of $r^{\prime }$. Namely, suppose there exists such a rectangle, then let $r^{\prime \prime }$ be the leftmost such rectangle. With the same argument as before, as $\mathrm{\ell }$ is a proper horizontal line in $H_i$, the bottom face of $r^{\prime \prime }$ is also below $\mathrm{\ell }$. Furthermore, $r^{\prime \prime }$ must be supported on the left, but as $r^{\prime \prime }$ is the leftmost rectangle, such a supporter is the left strip boundary, a contradiction to the definition of $r^{\prime }$. This implies that just before $r_i$ is placed, the space above $r^{\prime }$ is unoccupied, and $w_{r^{\prime }}\ge w_{r_i}$ by the decreasing width ordering of $𝒬$, hence $r_i$ could have been placed lower on top of $r^{\prime }$ by the BL algorithm. This contradiction implies that the leftmost part of the line $\mathrm{\ell }$ must be occupied by a rectangle. $◀$

Since $r_{a+1}$ is the first rectangle that is placed from $𝒬$, it follows that the bottom supporter $r_B$ is a rectangle from $ℱ$. It follows that $h_{r_{a+1}}\le h_{r_B}$, as otherwise $r_{a+1}$ would have been part of $ℱ$. As $𝒬$ is ordered by decreasing width, it holds for any rectangle $r\in 𝒬$ that $w_r\le w_{r_{a+1}}$. Therefore, it must hold that $h_r\le h_{r_B}$, as else $r$ would belong to $ℱ$. $◀$

This yields an upper bound on the height at which the left rectangle $r_L$ can be placed.

The statement is certainly true if $r_L=r_{a+1}$. Thus, we may assume that there is at least one rectangle in $𝒬$ that is placed before $r_L$; let $r\in 𝒬$ be the leftmost such rectangle whose left face touches the right face of a rectangle from $ℱ$. If there are multiple such rectangles, then let $r$ be the top one. Observe that by Lemma 10 the top face of $r$ is at most at height $h_{\max }+h_{r_B}$. There are two options. If there exists a rectangle in $𝒬$ that is placed to the left of $r$, then the first such rectangle must be $r_L$ because the only available left supporter left of $r$ is the left strip boundary by definition of $r$. Otherwise, the space left of $r$ is not occupied by rectangles from $𝒬$. Now, the first rectangle that is placed above $r$ (if it exists) must be placed on top of $r$ and must touch the left strip boundary; because the width of such a rectangle is less or equal to the width of $r$. In conclusion, either there is a first rectangle in $𝒬$ touching the left strip boundary, which then is placed at height at most $h_{\max }+h_{r_B}$; or there is no such rectangle, and then the bottom face of $r_L=r_T$ is placed below the top face of $r$, implying that . $◀$

Next, we study the properties of horizontal lines that intersect a fixed number of rectangles just before placing a rectangle above the line. To this end, define the type of a proper horizontal line $\mathrm{\ell }$ as the set $T(\mathrm{\ell })$ of rectangles from $𝒬$ that intersect $\mathrm{\ell }$ prior to placing the first rectangle above $\mathrm{\ell }$. If the cardinality of $T(\mathrm{\ell })$ equals $k$, then we say that the line $\mathrm{\ell }$ has order $k$. Moreover, denote by $LM(\mathrm{\ell })$ the leftmost rectangle from $T(\mathrm{\ell })$.

Suppose not, then there is a rectangle from $𝒬$ that is the left supporter of $LM(\mathrm{\ell })$. Let $r$ be such a left supporter with highest $y_r$ and let $r^{\prime }$ be the first rectangle that is placed above $\mathrm{\ell }$. Then it holds that $w_r\ge w_{r^{\prime }}$. Prior to placing $r^{\prime }$, no rectangle intersects $\mathrm{\ell }$ to the left of $LM(\mathrm{\ell })$, and no rectangle is above $\mathrm{\ell }$. As $\mathrm{\ell }$ is a proper line and the space to the left of $LM(\mathrm{\ell })$ is larger than $w_{r^{\prime }}$, it follows that $r^{\prime }$ can be placed with its bottom face below $\mathrm{\ell }$ to the left of $LM(\mathrm{\ell })$, contradicting that $r^{\prime }$ is above $\mathrm{\ell }$. $◀$

For two horizontal lines $\mathrm{\ell }$ and ${\mathrm{\ell }}^{\prime }$, we denote when $\mathrm{\ell }$ is below ${\mathrm{\ell }}^{\prime }$.

Suppose that , then the BL algorithm places $r^{\prime }$ before $r$. As $r\in T(\mathrm{\ell })$ is placed before the first rectangle is placed above $\mathrm{\ell }$, it follows that $r^{\prime }$ must intersect $\mathrm{\ell }$. However, this contradicts $r^{\prime }\notin T(\mathrm{\ell })$. $◀$

Let ${ℒ}^k$ be the set of all proper horizontal lines of order $k$ inside of the space $H_{a+2}\cup \mathrm{\cdots }\cup H_L$. Define ${ℛ}^k=\{r\in 𝒬\mid \exists \mathrm{\ell }\in {ℒ}^k:r=LM(\mathrm{\ell })\}$, that is, the set of all rectangles in $𝒬$ that are the leftmost rectangle of some line of order $k$. Furthermore, we denote by $L{M}^k$ the leftmost rectangle from ${ℛ}^k$, and if there are multiple such rectangles, then let $L{M}^k$ be the highest among them.

Suppose that $LM(\mathrm{\ell })\ne L{M}^k$. Lemma 12 states that each rectangle in ${ℛ}^k$ has a rectangle from $ℱ$ as left supporter. As the rectangles in $ℱ$ are placed from left to right by decreasing height, it follows that $L{M}^k$ also has the highest bottom face among all the rectangles in ${ℛ}^k$. Let ${\mathrm{\ell }}^{\prime }\in {ℒ}^k$ be a line intersecting $L{M}^k$.

Let $T(\mathrm{\ell })=\{r_{i_1},\mathrm{\dots },r_{i_k}\}$ and $T({\mathrm{\ell }}^{\prime })=\{r_{i_1^{\prime }},\mathrm{\dots },r_{i_k^{\prime }}\}$ ordered from left to right. There can be at most $k+1$ gaps on line $\mathrm{\ell }$ respectively ${\mathrm{\ell }}^{\prime }$ just before the first rectangle is placed above the line, namely, at most one to the left of $r_{i_1}$ (resp. $r_{i_1^{\prime }}$), at most one between each consecutive pair of rectangles from the type, and at most one to the right of $r_{i_k}$ (resp. $r_{i_k^{\prime }}$). Denote these gaps from left to right (with possibly length $0$) by $g_0,\mathrm{\dots },g_k$ respectively $g_0^{\prime },\mathrm{\dots },g_k^{\prime }$. We have that $x_{r_{i_1^{\prime }}}\le x_{r_{i_1}}-g_0$, because $x_{r_{i_1^{\prime }}}\le x_{r_{i_1}}$ and both have a rectangle from $ℱ$ as left supporter by Lemma 12. This implies that

Now, Lemma 13 implies that ${\sum }_{j=1}^k{w}_{r_{i_j}}\ge {\sum }_{j=1}^k{w}_{r_{i_j^{\prime }}}$. Thus it follows that

Moreover, we know that each gap on ${\mathrm{\ell }}^{\prime }$ has length less than the width of any rectangle adjacent to the gap just after the first rectangle is placed above ${\mathrm{\ell }}^{\prime }$. As those rectangles have width less than or equal to the rectangles intersecting $\mathrm{\ell }$, it follows that

Thus the line $\mathrm{\ell }$ is at least half occupied, which proves the first statement. Figure 2 illustrates this for $k=2$.

$◀$

Consequences of Lemma 3 respectively Lemma 14. $◀$

Suppose that the first statement is false, then there exist $\mathrm{\ell }\in {ℒ}^k$ and ${\mathrm{\ell }}^{\prime }\in {ℒ}^{k^{\prime }}$ with and $k>k^{\prime }$, such that for every ${\mathrm{\ell }}^{\prime \prime }\in {ℒ}^{k^{\prime \prime }}$ with it holds that $T({\mathrm{\ell }}^{\prime \prime })=T(\mathrm{\ell })$ or $T({\mathrm{\ell }}^{\prime \prime })=T({\mathrm{\ell }}^{\prime })$. This means that all rectangles in $T({\mathrm{\ell }}^{\prime })\setminus T(\mathrm{\ell })$ are placed on top of rectangles of $ℱ\cup T(\mathrm{\ell })\setminus T({\mathrm{\ell }}^{\prime })$. Consider the following assignment: go over the rectangles in $r^{\prime }\in T({\mathrm{\ell }}^{\prime })\setminus T(\mathrm{\ell })$ from left to right, and assign a rectangle $r\in T(\mathrm{\ell })\setminus T({\mathrm{\ell }}^{\prime })$ to $r^{\prime }$ if $r^{\prime }$ is the first rectangle in this ordering of $T({\mathrm{\ell }}^{\prime })\setminus T(\mathrm{\ell })$ that is above $r$. By definition, a rectangle from $T({\mathrm{\ell }}^{\prime })\setminus T(\mathrm{\ell })$ cannot be matched with two rectangles, because then it cannot have a left supporter as its width is less than the width of the rectangles from $T(\mathrm{\ell })\setminus T({\mathrm{\ell }}^{\prime })$ by Lemma 13. Thus each rectangle is matched with at most one other rectangle, but then as $k>k^{\prime }$, there must be a rectangle in $T(\mathrm{\ell })\setminus T({\mathrm{\ell }}^{\prime })$ that has no rectangle from $T({\mathrm{\ell }}^{\prime })\setminus T(\mathrm{\ell })$ on top of it, and therefore, the first rectangle that is placed above ${\mathrm{\ell }}^{\prime }$ can now be placed lower on top of this free rectangle. Contradiction.

Next suppose that $k\ne k^{\prime }$. Let $r$ be the rightmost rectangle from $ℱ$ intersecting $\mathrm{\ell }$. Then $x_{LM({\mathrm{\ell }}^{\prime })}\le x_r+w_r$, because $ℱ$ is placed in order of decreasing height, ${\mathrm{\ell }}^{\prime }$ is above $\mathrm{\ell }$ and both have a left supporter in $ℱ$ by Lemma 12. This immediately implies that the downward projections are disjoint, since the first gap on ${\mathrm{\ell }}^{\prime }$ ends at $x_{LM({\mathrm{\ell }}^{\prime })}$, and the first gap on $\mathrm{\ell }$ begins at $x_r+w_r$. $◀$

To measure the distance between two horizontal lines, we denote by $d(\mathrm{\ell },{\mathrm{\ell }}^{\prime })$ the difference in $y$-coordinates.

By Corollary 15 the space $H_{a+2}\cup \mathrm{\cdots }\cup H_L$ is maximally unoccupied when we have for all $k$ that $|{ℛ}^k|\le 1$, because only lines of order $k$ intersecting the leftmost rectangle of ${ℛ}^k$ can be $(k+1)/(2k+1)$ unoccupied, while other lines of order $k$ are only at most half unoccupied.

Define ${\alpha }_k=sup\{d(\mathrm{\ell },{\mathrm{\ell }}^{\prime })\mid \mathrm{\ell },{\mathrm{\ell }}^{\prime }\in {ℒ}^k\text{ s.t. }L{M}^k\in T(\mathrm{\ell })\cap T({\mathrm{\ell }}^{\prime })\}$, that is, the largest distance between two lines of order $k$ that both intersect the leftmost rectangle of ${ℛ}^k$. If no line of order $k$ exists, then define ${\alpha }_k=0$. From Lemma 14 it follows that all lines of order $k$ that are less than half occupied are considered in this supremum. It holds that ${\alpha }_k\le h_{L{M}^k}\le \frac{1}{2}{h}_{\text{OPT}}$ by Lemma 4. Furthermore, the height of the space $H_{a+2}\cup \mathrm{\cdots }\cup H_L$ is $h$ by definition, thus ${\sum }_{k=1}^{\mathrm{\infty }}{\alpha }_k=h$. Notice that for an instance consisting of $n$ rectangles, it holds that ${\alpha }_k=0$ for any $k>n$, hence ${\sum }_{k=1}^{\mathrm{\infty }}{\alpha }_k$ equals the finite sum ${\sum }_{k=1}^n{\alpha }_k$. In conclusion, we have the linear constraints ${\alpha }_k\le \frac{1}{2}{h}_{\text{OPT}}$ for every $k$ and ${\sum }_{k=1}^{\mathrm{\infty }}{\alpha }_k=h$.

Next, consider $\mathrm{\ell }\in {ℒ}^k$ that is less than half occupied. This line might intersect some rectangles $r_1,\mathrm{\dots },r_z$ from $ℱ$ and it intersects $k$ rectangles $r_{i_1},\mathrm{\dots },r_{i_k}$ from $𝒬$ prior to placing the first rectangle above $\mathrm{\ell }$ (see Figure 3). We define $x_{ℱ}^{\mathrm{\ell }}=x_{r_z}+w_{r_z}$ if $r_z$ exists, and otherwise we define $x_{ℱ}^{\mathrm{\ell }}=0$. By Lemma 2 at this moment, each gap between rectangles has width strictly less than the width of the smallest rectangle from $𝒬$ that intersects the line $\mathrm{\ell }$. Hence, there exists an $x$-coordinate $x_{\mathrm{\ell }}\in [x_{ℱ}^{\mathrm{\ell }},x_{r_{i_1}}]$ such that the line $\mathrm{\ell }$ is exactly half occupied to the right of $x_{\mathrm{\ell }}$. Define the length of the remaining gap on the line by ${\beta }^{\mathrm{\ell }}=x_{\mathrm{\ell }}-x_{ℱ}^{\mathrm{\ell }}$.

Furthermore, for all lines of order $k$ that are less than $W/2$ occupied, consider the largest such ${\beta }^{\mathrm{\ell }}$-gap

Again define ${\beta }_k=0$ if ${ℒ}^k$ is empty. It holds that the gap ${\beta }_k$ is upper bounded by $\frac{1}{2k+1}W$, because by Lemma 3 a line of order $k$ is at most $\frac{k}{2k+1}W$ occupied and each rectangle on the line is larger than any unoccupied gap on the line. Moreover, it holds that ${\sum }_{k=1}^{\mathrm{\infty }}{\beta }_k\le W$, because for different values of $k$ the downward projections of the gaps defined by ${\beta }_k$ are disjoint by Lemma 16.

Next we describe the relation between the amount of unoccupied space and the values $\alpha$ and $\beta$. A line $\mathrm{\ell }$ of order $k$ has exactly ${\beta }^{\mathrm{\ell }}+\frac{1}{2}\left(W-x_{\mathrm{\ell }}\right)$ unoccupied space (see Figure 3). By definition it holds that ${\beta }^{\mathrm{\ell }}\le {\beta }_k$. Furthermore, we have $x_{\mathrm{\ell }}\ge {\sum }_{j=k}^{\mathrm{\infty }}{\beta }_j$, because the rightmost point of the ${\beta }_{j+1}$-gap is left of the leftmost point of the ${\beta }_j$-gap for all $j$ by Lemma 16. Therefore, $\mathrm{\ell }$ has at most ${\beta }_k+\frac{1}{2}\left(W-{\sum }_{j=k}^{\mathrm{\infty }}{\beta }_j\right)$ unoccupied space. At most ${\alpha }_k$ of the lines of order $k$ are more than half unoccupied by Lemma 14. Hence the maximum amount of unoccupied space in $H_{a+2}\cup \mathrm{\cdots }\cup H_L$ is a solution to the following quadratic program

The objective of this quadratic program can be rewritten as

Let $k_1$ and $k_2$ be different indices such that ${\gamma }_{k_1}\ge {\gamma }_{k_2}\ge {\gamma }_k$ for all $k\in \mathbb{N}\setminus \{k_1\}$. Then setting ${\alpha }_{k_1}=\min \{\frac{1}{2}{h}_{\text{OPT}},h\}$, ${\alpha }_{k_2}=\max \{0,h-\frac{1}{2}{h}_{\text{OPT}}\}$ and ${\alpha }_k=0$ for $k\in \mathbb{N}\setminus \{k_1,k_2\}$ maximizes the objective (provided that ${\gamma }_{k_1},{\gamma }_{k_2}\ge 0$), because by Lemma 11 we have that $h=y_{r_L}-y_{r_{a+1}}\le h_{\text{max}}\le h_{\text{OPT}}$, as $r_B$ is the leftmost bottom supporter of $r_{a+1}$. If $h\le \frac{1}{2}{h}_{\text{OPT}}$, then ${\alpha }_{k_2}=0$ and the maximum objective value is $\frac{1}{2}h{\gamma }_{k_1}=\frac{2}{3}hW$ when $k_1=1$, ${\beta }_1=\frac{1}{3}W$ and ${\beta }_k=0$ for all $k\ge 2$. And observe that $\frac{2}{3}hW=\frac{1}{2}hW+\frac{1}{6}hW\le \frac{1}{2}hW+\frac{1}{12}{h}_{\text{OPT}}W$ as $h\le \frac{1}{2}{h}_{\text{OPT}}$. Otherwise, if $h>\frac{1}{2}{h}_{\text{OPT}}$, then the objective is $\frac{1}{4}{h}_{\text{OPT}}{\gamma }_{k_1}+\frac{1}{2}(h-\frac{1}{2}{h}_{\text{OPT}}){\gamma }_{k_2}$. There exists a maximum solution with ${\beta }_k=0$ for $k\notin \{k_1,k_2\}$, because ${\beta }_k>0$ only increases the objective when ${\alpha }_k>0$, which is only the case for $k\in \{k_1,k_2\}$. Thus if , then, as $h\le h_{\text{OPT}}$, the objective becomes

and in case $k_1>k_2$, the objective is

This is maximum for $\min \{k_1,k_2\}=1$ and ${\beta }_{\min \{k_1,k_2\}}=\frac{1}{3}W$. This also gives the desired result $\frac{1}{12}{h}_{\text{OPT}}W+\frac{1}{2}hW$. $◀$

Consider the packing $\text{BL}({ℐ}_{ℱ𝒬𝒲})$. If $𝒬=\mathrm{\varnothing }$ or $y_r+h_r\le h_{\text{max}}$ for all $r\in 𝒬$, then Lemma 5 implies that the BL algorithm is a $2$-approximation. Hence assume that $𝒬\ne \mathrm{\varnothing }$ and $\max \{y_r+h_r\mid r\in 𝒬\}>h_{\text{max}}$. The space $H^{\prime }$ defined in Lemma 8 is contained in $H_{a+1}\cup H_L\cup \mathrm{\cdots }\cup H_{a+b+1}$ by Lemma 10. Thus, Lemma 6, 7, 8 and 9 imply that the space $H_{a+1}\cup H_L\cup \mathrm{\cdots }\cup H_{a+b+1}$ is at least half occupied by rectangles. Furthermore, for $h=y_{r_L}-y_{r_{a+1}}$, Theorem 17 states that the space $H_{a+2}\cup \mathrm{\cdots }\cup H_L$ is at least $\frac{1}{2}hW-\frac{1}{12}{h}_{\text{OPT}}W$ occupied. Thus the BL algorithm covers at least an area of

As the total area covered by rectangles divided by $W$ is a lower bound for $h_{\text{OPT}}$ we get that

This implies the desired approximation guarantee

$◀$