[1]Rachel Vanucchi Saraiva

These authors contributed equally to this work.

[1]Institute of Computing, University of Campinas, Av. Albert Einstein, 1251,
Campinas, 13083-852, São Paulo, Brazil

# Approximation algorithms for the square min-sum bin packing
problem$\ddagger$

0000-0001-6197-603X<EMAIL_ADDRESS>Rafael C. S. Schouery
0000-0002-0472-4810<EMAIL_ADDRESS>*

###### Abstract

In this work, we study the square min-sum bin packing problem (SMSBPP), where
a list of square items has to be packed into indexed square bins of dimensions
$1\times 1$ with no overlap between the areas of the items. The bins are
indexed and the cost of packing each item is equal to the index of the bin in
which it is placed in. The objective is to minimize the total cost of packing
all items, which is equivalent to minimizing the average cost of items. The
problem has applications in minimizing the average time of logistic operations
such as cutting stock and delivery of products. We prove that classic
algorithms for two-dimensional bin packing that order items in non-increasing
order of size, such as Next Fit Decreasing Height or Any Fit Decreasing Height
heuristics, can have an arbitrarily bad performance for SMSBPP. We, then,
present a $\frac{53}{22}$-approximation and a PTAS for the problem.

###### keywords:

Approximation algorithm, Bin Packing, Square Packing, Completion Time

††$\ddagger$Supported by Grants 311039/2020-0 and 163644/2021-7, National
Council for Scientific and Technological Development (CNPq). This study was
financed in part by the Coordenação de Aperfeiçoamento de Pessoal de Nível
Superior - Brasil (CAPES) - Finance Code 001.

##  1 Introduction

The bin packing problem (BPP) is a classic NP-hard problem where a list of
items with varying sizes must be packed into bins of identical capacity. It
models relevant logistic problems for industries such as the storage of
products and digital files, loading of cargo into vehicles, task scheduling on
several machines, and many others [4].

In classic BPP, the goal is to minimize the number of bins needed to pack all
items, which, in real applications, leads to minimizing storage costs and
waste of resources. [6] defined the min-sum bin packing problem (MSBPP), where
bins are indexed and the cost of packing an item is equal to the index of the
bin in which it is placed. The objective is to minimize the total cost of
packing all items, which is equivalent to minimizing the average cost of the
items. For example, if each bin represents the items a single vehicle carries
for one trip, and the indexes represents the order of the trips the vehicle
makes, then the solution of MSBPP minimizes the average number of trips that
it takes to transport an item.

The same authors have also defined a weighted version of the problem, the
minimum weighted sum bin packing problem (MWSBPP), where each item has an
associated weight to it, and the cost of packing an item is the index of the
bin in which it is placed multiplied by the weight of the item. This
represents the idea that certain items might have priority over others and
should be packed first. MWSBPP is also equivalent to a batch-scheduling
problem where a machine can process, in parallel, a batch of jobs of size at
most $1$, and the objective is to minimize the weighted sum of completion
times. This problem is noted as $1|p\text{-\emph{batch}},s_{j},p_{j}=1|\sum
w_{j}C_{j}$ in the three-field notation for batch scheduling introduced by
[9]. For more details on batch scheduling, we refer to the recent survey done
by [8].

Both MSBPP and MWSBPP define items and bins as one-dimensional, that is, each
item is associated with a single size, and the sum of the sizes of all items
packed in a bin cannot exceed the capacity of the bin. In this paper, we
define the square min-sum bin packing problem (SMSBPP) as follows: the input
is a list of $n$ square items. We define the size of a square as the size of
its height (and thus also its width) and, for $i$ such that $1\leq i\leq n$,
the size of the $i$-th square in the list is $s_{i}\in(0,1]$. All items in the
list must be packed in indexed square bins $B_{1},\dots,B_{m}$ of side $1$,
and the cost of packing an item in $B_{j}$ is $j$. The objective is to
minimize the total cost ${\sum_{j=1}^{m}j\cdot|B_{j}|}$ of packing all items,
in which $|B_{j}|$ is the amount of items packed in bin $B_{j}$. A feasible
packing of items in a bin is one where all items are within the internal area
of the bin, with no intersection between the internal area of an item with the
borders of the bin or between the internal areas of any two items. Items are
packed with their sides parallel to the sides of the bin. These constraints
capture extra challenges not represented by the one-dimensional definition
when it comes to the placement of physical items in a bin.

In the following section, we discuss previous works related to min-sum and
square bin packing. In Section 3, we present a $\frac{53}{22}$-approximation
for SMSBPP, and, in Section 4, a PTAS for the problem. Finally, in Section 5
we discuss our conclusions from the study and present directions for future
work.

##  2 Preliminary work

To the best of our knowledge, there is no previous work on min-sum bin packing
with items and bins with more than one dimension. For MWSBPP, [6] present a
PTAS and a Dual-PTAS. As for MSBPP, [5] present a Next Fit Increasing
heuristic with an absolute approximation ratio of at most $2$ and an
asymptotic approximation ratio of at most $1.6188$, along with a heuristic
with an asymptotic approximation ratio of at most $1.5604$. The authors also
presents a PTAS for MSBPP similar to the one for MWSBPP.

Much work exists in relation to classic BPP with multidimensional items and
bins. We refer to the survey done by [2] for further details on approximation
algorithms for the problem. For the packing of two-dimensional items, we will
focus on level-oriented heuristics which pack items into levels within the
bin. A level is a strip with width equal to the width of the bin, and height
equal to the first item packed in the level. Usually, the items are also
ordered by non-increasing order of height.

Among these heuristics, there is Next Fit Decreasing Height (NFDH), where
items are packed in the current level until an item cannot fit in, which leads
to a new level being opened. The previous levels do not receive any additional
items. Similarly, a new bin is only opened once it cannot fit a new level, and
once it is opened no levels are created in the previous bins as well.

Other level-oriented heuristics are those from the family Any Fit Decreasing
Height (AFDH), where a new level is only opened if the current item cannot fit
in any of the previous levels, and, similarly, a new bin is only opened when a
level will not fit in any of the previous bins.

For NFDH, [3] show that, if $\delta$ is an upper bound on the areas of the
items packed by the algorithm, then the unoccupied area left in every bin
except possibly the last one is at most $2\delta$. [11] has also proved that,
if the items packed by NFDH are all squares of size at most $1/3$, then the
area occupied in every bin, except possibly the last one, is at least $9/16$.
We use NFDH and these results in our proposed algorithms, however we also
prove in the following lemma that NFDH and AFDH heuristics alone do not have a
constant approximation ratio for SMSBPP, as ordering items by non-increasing
order of size is clearly unhelpful for this problem. The solution given by
NFDH can, however, have its value greatly reduced by reordering the bins in
non-increasing order of the amount of items after packing.

######  Lemma 1.

NFDH and AFDH heuristics do not have a constant approximation ratio for
SMSBPP.

###### Proof.

Let $t\geq 3$ be an integer. We create an instance $I$ of SMSBPP with $t^{2}$
items of size $1/t$, which we refer to as small items from here on, and $t$
items of size ${1-1/t}$, which we refer to as large items. Any AFDH heuristic
will first pack one large item per bin, since two large items cannot fit
together in a same bin. Each bin can then still fit $t+1$ small items, one in
the same level as the large item, and $t$ in a new level above it. Therefore,
$t$ bins are used to pack all the items, $t-1$ of them containing $t+2$ items,
and the last one containing $2$ items. Figure 1 shows an example of this
packing. The value of the solution is, therefore,

$\mathrm{AFDH}(I)=\sum_{j=1}^{t-1}j\cdot(t+2)+2t=\frac{t^{3}+t^{2}+2t}{2}.$

Now consider another solution, also depicted in Figure 1, where all small
items are packed in the first bin, and, then, $t$ bins are opened to pack one
large item each. The value of this solution is

$t^{2}+\sum_{j=2}^{t+1}j=t^{2}+\frac{(t+3)t}{2}=\frac{3t^{2}+3t}{2}\geq\mathrm{OPT}(I),$

in which $\mathrm{OPT}(I)$ is the value of an optimal solution for $I$.

[scale=0.5] (0, 0) rectangle (3, 3); (4, 0) rectangle (7, 3); (8, 0) rectangle
(11, 3);

[draw=black, fill=lightgray] (0, 0) rectangle (2,2); [draw=black,
fill=lightgray] (4, 0) rectangle (6,2); [draw=black, fill=lightgray] (8, 0)
rectangle (10,2);

[draw=black, fill=lightgray] (2, 0) rectangle (3,1); [draw=black,
fill=lightgray] (6, 0) rectangle (7,1); [draw=black, fill=lightgray] (10, 0)
rectangle (11,1);

[draw=black, fill=lightgray] (0, 2) rectangle (3,3); [draw=black,
fill=lightgray] (4, 2) rectangle (7,3);

ıin 1,…,2 (1*ı, 2) – (1*ı, 3); (4+1*ı, 2) – (4+1*ı, 3); [draw=white] (0,-1) –
(1, -1); [scale=0.5] [draw=black, fill=gray] (0, 0) rectangle (3, 3); (4, 0)
rectangle (7, 3); (8, 0) rectangle (11, 3); (12, 0) rectangle (15, 3);

[draw=black, fill=gray] (4, 0) rectangle (6, 2); [draw=black, fill=gray] (8,
0) rectangle (10, 2); [draw=black, fill=gray] (12, 0) rectangle (14, 2);

(0,1) – (3,1); (0,2) – (3,2); (1,0) – (1,3); (2,0) – (2,3);

Figure 1: Packing of $I$ with $t=3$ done by an AFDH heuristic (above) compared
to another possible packing (below).

Therefore, the approximation ratio of any AFDH heuristic is at least

$\frac{\mathrm{AFDH}(I)}{\mathrm{OPT}(I)}\geq\frac{t^{3}+t^{2}+2t}{2}\cdot\frac{2}{3t^{2}+3t}\geq\frac{t}{3}.$

The NFDH heuristic also first packs one large item per bin. Then, only the
last of these bins packs $t+1$ small items, and the remaining $t^{2}-t-1$
small items are packed in a new bin, as shown in Figure 2. Thus, the value of
the solution is

$\displaystyle\mathrm{NFDH}(I)$
$\displaystyle=\sum_{j=1}^{t-1}j+t(t+2)+(t+1)(t^{2}-t-1)$
$\displaystyle=\frac{2t^{3}+3t^{2}-t-2}{2}.$

[scale=0.5] (0, 0) rectangle (3, 3); (4, 0) rectangle (7, 3); (8, 0) rectangle
(11, 3); (12, 0) rectangle (15, 3);

[draw=black, fill=gray] (0, 0) rectangle (2, 2); [draw=black, fill=gray] (4,
0) rectangle (6, 2); [draw=black, fill=gray] (8, 0) rectangle (10, 2);

[draw=black, fill=gray] (8, 2) rectangle (11,3); [draw=black, fill=gray] (10,
0) rectangle (11,1);

[draw=black, fill=gray] (12, 1) rectangle (14,2); [draw=black, fill=gray] (12,
0) rectangle (15,1);

(9, 2) – (9,3); (10, 2) – (10,3);

(13, 0) – (13,2); (14, 0) – (14,2); (12, 2) – (15,2);

Figure 2: Packing of $I$ with $t=3$ done by NFDH.

Since $2t^{2}>t+2$ for every $t\geq 2$, the approximation ratio of NFDH is at
least

$\frac{\mathrm{NFDH}(I)}{\mathrm{OPT}(I)}\geq\frac{2t^{3}+3t^{2}-t-2}{3t^{2}+3t}>\frac{2t^{3}+t^{2}}{3t^{2}+3t}>\frac{t}{3}.$

For this particular instance, if the bins of the NFDH solution are ordered in
non-increasing order of the amount of items, then its value becomes

$\displaystyle
t^{2}-t-1+2(t+1)+\sum_{j=3}^{t+1}j=\frac{3t^{2}}{2}+\frac{5t}{2}-1,$

which is much closer to our bound on $\mathrm{OPT}(I)$. ∎

[1] have proved that there is no APTAS for the general case of BPP with two-
dimensional items. They have, however, also proved the existence of an APTAS
for the packing of $d$-dimensional cubes into unit $d$-dimensional bins.

On the topic of packing square items, [10] have shown that NFDH and AFDH
heuristics can fit a set of items of total area at most $1/2$ into a single
bin. [7] have presented the First Fit Decreasing Size (FFDS) algorithm for
optimal packing of items of size greater than $1/3$. The way the algorithm
works is described as follows. It orders the items of size greater than $1/2$
in non-decreasing order of size and packs them one per bin, in the bottom left
corner of the bin. Then, it orders the remaining items in non-increasing order
of size and checks if the first item in the list fits in any of the bins
already opened. If it fits, then the three first items of the list are packed
into the first bin they fit, one in each unoccupied corner of the bin. If the
item doesn’t fit any existing bin, then a new bin is opened and the four first
items of the list are packed in it. The process then repeats until all items
have been packed. Figure 3 shows an example of a packing by FFDS.

[scale=0.5] (0, 0) rectangle (4, 4); (5, 0) rectangle (9, 4); (10, 0)
rectangle (14, 4); [draw=black, fill=lightgray] (0, 0) rectangle (2.3, 2.3);
[draw=black, fill=lightgray] (5, 0) rectangle (7.5, 2.5); [draw=black,
fill=gray] (2.5, 0) rectangle (4, 1.5); [draw=black, fill=gray] (0, 2.5)
rectangle (1.5, 4); [draw=black, fill=gray] (2.5, 2.5) rectangle (4, 4);

[draw=black, fill=gray] (10, 0) rectangle (12, 2); [draw=black, fill=gray]
(12.1, 0) rectangle (14, 1.9); [draw=black, fill=gray] (10, 2.1) rectangle
(11.9, 4); [draw=black, fill=gray] (12.2, 2.2) rectangle (14, 4);

Figure 3: Example of packing done by FFDS.

Note that $4$ is the maximum amount of items of size greater than $1/3$ that
can be packed in a single bin, and FFDS packs as many bins with this amount of
items as it is possible. Therefore, if we reorder the bins of the FFDS packing
in non-increasing order of the amount of items, the solution is also optimal
for an instance of SMSBPP with these items. Combining NFDH and FFDS, [11]
presents a $2$-approximation for BPP with square items. We use a similar
approach in our $\frac{53}{22}$-approximation for SMSBPP in the following
section.

##  3 A $\frac{53}{22}$-approximation

We now present a $\frac{53}{22}$-approximation for SMSBPP. We assume ${n\geq
266730}$, as otherwise the size of the instance is limited by a constant, and
thus the possible partitions of items can be enumerated in constant time. It
is also possible to test in constant time if a subset with a constant amount
of items can be feasibly packed into a bin, and, therefore, an optimal
solution for the instance can be found by exhaustive enumeration in constant
time. Despite that, we will also show that, for instances where ${n<266730}$,
the algorithm proposed below returns a packing of value less than
$\frac{53}{22}\mathrm{OPT}(I)+27769$.

The algorithm is described as follows. First, we classify items according to
their size. Items of size at most $1/3$ are small items, items of size greater
than $1/2$ are large items, and the remaining are medium items. We also define
$\mathrm{AREA}(C)$ as the sum of the areas of items in a set $C$. We order the
items in non-decreasing order of their sizes and then divide them into groups
$G_{1},\dots,G_{q}$ such that each group $G_{i}$ receives items until
$\mathrm{AREA}(G_{i})>1$, or until there are no more items in the instance
(for the final group).

Let $r$ be the amount of groups containing only small items, and let
$G^{S}_{r+1}$ be the set of small items in $G_{r+1}$. We pack the items of
each group $G_{1},\dots,G_{r}$ and $G^{S}_{r+1}$ in order with NFDH.
Afterward, we pack the large and medium items with FFDS, and sort the solution
found by FFDS in a non-increasing order of the amount of items. Finally, we
place the bins of the packing found with FFDS for medium and large items after
the packing found by NFDH for small items. As both NFDH and FFDS can be
implemented with time complexity $O(n\log n)$ [7], the complexity of our
algorithm is also $O(n\log n)$.

###  3.1 Bounds

Let $A(I)$ be the value of the solution given by our algorithm for an instance
$I$. For analysis of the approximation ratio, we now find lower bounds
$\mathrm{LB}_{1}$ and $\mathrm{LB}_{2}$ on $\mathrm{OPT}(I)$ such that
${A(I)-\alpha\mathrm{LB}_{1}-(\frac{53}{22}-\alpha)\mathrm{LB}_{2}\leq 0}$ for
some ${0\leq\alpha\leq\frac{53}{22}}$, as that implies
$A(I)\leq\frac{53}{22}\mathrm{OPT}(I)$ and thus the algorithm is a
$\frac{53}{22}$-approximation.

The first bound $\mathrm{LB}_{1}=\sum_{i=1}^{q}i|G_{i}|$ is obtained from the
definition of the groups $G_{i}$. As [5] have shown, if
$\mathrm{AREA}(G_{i})>1$, no feasible solution can pack more than
${\sum_{i=1}^{t}}|G_{i}|$ items in the first $t$ bins, and so the following
lemma applies.

######  Lemma 2 (Epstein et al., 2018).

$\mathrm{OPT}(I)\geq\sum_{i=1}^{q}i|G_{i}|$.

As mentioned before, every bin with only small items packed by NFDH except
possibly the last one has occupied area of at least $9/16$ [11]. Since the
area of any small item is at most $1/9$ and $\mathrm{AREA}(G_{i})$ is greater
than $1$ by a single item, $\mathrm{AREA}(G_{i})\leq 10/9<9/8$ for $i\leq r$,
and ${\mathrm{AREA}(G^{S}_{r+1})\leq 1}$. Therefore, for $i\leq r+1$, the
small items of the first $i$ groups are packed by NFDH in at most $2i$ bins
and the cost of a small item of $G_{i}$ in this packing is at most $2i$. Thus,
the total cost of packing all small items by our algorithm is at most

$\sum_{i=1}^{r}2i|G_{i}|+(2r+2)|G^{S}_{r+1}|.$

By Lemma 2, this means the algorithm is a$2$-approximation for instances with
only small items.

The lower bound given by Lemma 2 is, however, less helpful for the analysis of
instances with large items, as a group $G_{i}$ can contain up to four large
items, and yet only a single large item can be packed in each bin, thus their
cost might be close to $4i$ in our packing. Because of that, we define another
lower bound on $\mathrm{OPT}(I)$ based on the fact that the packing of FFDS is
optimal for the subset of large and medium items of the instance.

Let $\mathrm{FFDS}(d)$ be the cost of packing large and medium items with FFDS
and bin reordering after a bin of index $d$ (if $d=0$, then the bins of FFDS
are the first bins in the solution). We make the following observation that,
for any solution, the cost of packing two disjunct subsets $A$ and $B$ of
items of the instance is at least the cost of an optimal solution for $A$ plus
the cost of an optimal solution for $B$.

######  Observation 1.

$\mathrm{OPT}(A\cup B)\geq\mathrm{OPT}(A)+\mathrm{OPT}(B)$.

By Lemma 2, $\sum_{i=1}^{r}i|G_{i}|+(r+1)|G^{S}_{r+1}|$ is a lower bound of
the cost of an optimal solution for the small items. The packing done by FFDS
is optimal for the large and medium items. Therefore, by Observation 1,
another lower bound, $\mathrm{LB}_{2}$, on the value of an optimal solution
for the whole instance is

$\mathrm{LB}_{2}=\sum_{i=1}^{r}i|G_{i}|+(r+1)|G^{S}_{r+1}|+\mathrm{FFDS}(0).$

We now develop the bound $\mathrm{LB}_{1}$ a little further based on the FFDS
packing. For ease of notation, let
$R=\sum_{i=1}^{r}i|G_{i}|+(r+1)|G^{S}_{r+1}|$. Let $k$ be the amount of medium
items in the instance plus the amount of large items packed in the same bin as
some medium item by FFDS, and let $b$ be the amount of large items packed
alone in a bin by FFDS. Since $\mathrm{AREA}(G_{i})$ is greater than $1$ by a
single item, any group $G_{i}$ contains at most $9$ medium items and at most
$4$ large items. Therefore, the amount of groups containing medium items plus
the large items packed with a medium item by FFDS is at least $\lfloor
k/9\rfloor$, and the amount of groups containing the large items packed alone
by FFDS is at least $\lfloor b/4\rfloor$. Thus, since $\lfloor k/9\rfloor\geq
k/9-1$ and $\lfloor b/4\rfloor\geq b/4-1$,

$\displaystyle\mathrm{LB}_{1}$ $\displaystyle=\sum_{i=1}^{q}i|G_{i}|$
$\displaystyle\geq R+\sum_{i=1}^{\lfloor k/9\rfloor}9(r+i)+\sum_{i=1}^{\lfloor
b/4\rfloor}4(r+\lfloor k/9\rfloor+i)$ $\displaystyle\geq
R+9r\left(\frac{k}{9}-1\right)+\frac{9\left(\frac{k}{9}-1\right)\frac{k}{9}}{2}$
$\displaystyle\quad+4\left(r+\frac{k}{9}-1\right)\left(\frac{b}{4}-1\right)+\frac{4\left(\frac{b}{4}-1\right)\frac{b}{4}}{2}$
$\displaystyle=R+rk-13r+\frac{k^{2}}{18}-\frac{17k}{18}+rb+\frac{kb}{9}-\frac{3b}{2}$
$\displaystyle\quad+4+\frac{b^{2}}{8}.$

###  3.2 Analysis of the algorithm

Having defined our lower bounds on $\mathrm{OPT}(I)$, we now bound the value
of the solution given by our algorithm. As mentioned before, the cost of
packing the small items with the algorithm is
$\sum_{i=1}^{r}2i|G_{i}|+(2r+2)|G^{S}_{r+1}|=2R$. Then the large and medium
items are packed by FFDS with bin reordering. Since at most $2r+2$ bins are
used to pack the small items,

$A(I)\leq 2R+\mathrm{FFDS}(2r+2).$

The amount of items packed by FFDS is $k+b$, and placing the solution after
$d$ bins raises the cost of each item by $d$ compared to a solution with only
the bins of FFDS. Therefore, we have the following observation.

######  Observation 2.

$\mathrm{FFDS}(d)=(k+b)d+\mathrm{FFDS}(0)$.

With this observation, we can begin comparing the value of the solution of our
algorithm with the bounds on $\mathrm{OPT}(I)$ we have previously obtained.

######  Lemma 3.

$A(I)-\mathrm{LB}_{2}-\frac{31}{22}\mathrm{LB}_{1}\leq-\frac{9}{22}R+\frac{13r(k+b)}{9}+\frac{1319k}{396}+\frac{181b}{44}+\frac{403r}{22}-\frac{31k^{2}}{396}-\frac{31kb}{198}-\frac{62}{11}-\frac{31b^{2}}{176}$.

###### Proof.

Recall that $A(I)\leq 2R+\mathrm{FFDS}(2r+2)$ and
$\mathrm{LB}_{2}(I)=R+\mathrm{FFDS}(0)$. By Observation 2, we have

$\displaystyle A(I)-\mathrm{LB}_{2}$ $\displaystyle\leq R+(k+b)(2r+2)$
$\displaystyle=R+2rk+2k+2rb+2b.$

We now recall that

$\mathrm{LB}_{1}\geq
R+rk-13r+\frac{k^{2}}{18}-\frac{17k}{18}+rb+\frac{kb}{9}-\frac{3b}{2}+4+\frac{b^{2}}{8}.$

Therefore,

$\displaystyle A(I)-\mathrm{LB}_{2}-\frac{31}{22}\mathrm{LB}_{1}$
$\displaystyle\leq-\frac{9}{22}R+\frac{13r(k+b)}{22}+\frac{1319k}{396}+\frac{181b}{44}+\frac{403r}{22}$
$\displaystyle\quad-\frac{31k^{2}}{396}-\frac{31kb}{198}-\frac{62}{11}-\frac{31b^{2}}{176},$

and the result follows. ∎

Let $s=\sum_{i=1}^{r}|G_{i}|+|G^{S}_{r+1}|$ be the amount of small items in
the instance, that is, $n=s+k+b$. The rest of the analysis is divided in two
cases depending on the values of $s$, $k$ and $b$. Since the bound on
$A(I)-\mathrm{LB}_{2}-\frac{31}{22}\mathrm{LB}_{1}$ given by Lemma 3 has the
negative terms $-\frac{31k^{2}}{396}$, $-\frac{31b^{2}}{176}$, and
$-\frac{31kb}{198}$, we start with the case in which the value of $k$ or $b$
is big enough to greatly lower the value of the expression.

######  Lemma 4.

If $k\geq 208$ or $b\geq 102$,
then$A(I)-\mathrm{LB}_{2}-\frac{31}{22}\mathrm{LB}_{2}<0$.

###### Proof.

Since $\mathrm{AREA}(G_{i})>1$ and any small item has area of at most $1/9$,
$|G_{i}|\geq 10$ for $i\leq r$. Thus,

$\displaystyle\frac{9}{22}R\geq\frac{9}{22}\sum_{i=1}^{r}i|G_{i}|\geq\frac{45}{11}\sum_{i=1}^{r}i$
$\displaystyle=\frac{45r(r+1)}{22}$
$\displaystyle=\frac{45r^{2}}{22}+\frac{45r}{22}.$

Therefore, by Lemma 3,

$\displaystyle A(I)-\mathrm{LB}_{2}-\frac{31}{22}\mathrm{LB}_{1}$
$\displaystyle\leq-\frac{45r^{2}}{22}+\frac{13r(k+b)}{22}+\frac{1319k}{396}+\frac{181b}{44}$
$\displaystyle\quad+\frac{179r}{11}-\frac{31k^{2}}{396}-\frac{31kb}{198}-\frac{62}{11}-\frac{31b^{2}}{176}.$

The derivative function of
$-\frac{45r^{2}}{22}+\frac{13r(k+b)}{22}+\frac{179r}{11}$ in $r$ is
$-\frac{45r}{11}+\frac{13(k+b)}{22}+\frac{179}{11}$, and so its maximum point
is $r=\frac{11}{45}\left(\frac{13(k+b)}{22}+\frac{179}{11}\right)$. In this
point,
$\frac{45r}{22}=\frac{1}{2}\left(\frac{13(k+b)}{22}+\frac{179}{11}\right)$,
and so

$\displaystyle-\frac{45r^{2}}{22}+\frac{13r(k+b)}{22}+\frac{179r}{11}$
$\displaystyle=\left(-\frac{45r}{22}+\frac{13(k+b)}{22}+\frac{179}{11}\right)r$
$\displaystyle=\frac{1}{2}\left(\frac{13(k+b)}{22}+\frac{179}{11}\right)\cdot\frac{11}{45}\left(\frac{13(k+b)}{22}+\frac{179}{11}\right)$
$\displaystyle=\frac{1859(k+b)^{2}}{43560}+\frac{2327(k+b)}{990}+\frac{32041}{990}$
$\displaystyle<\frac{k^{2}}{20}+\frac{kb}{10}+\frac{b^{2}}{20}+\frac{12k}{5}+\frac{12b}{5}+\frac{357}{11}.$

By replacing this inequality in our previous lower bound
on$A(I)-\mathrm{LB}_{2}-\frac{31}{22}\mathrm{LB}_{1}$, we obtain

$\displaystyle A(I)-\mathrm{LB}_{2}-\frac{31}{22}\mathrm{LB}_{1}$
$\displaystyle\leq-\frac{45r^{2}}{22}+\frac{13r(k+b)}{22}+\frac{1319k}{396}+\frac{181b}{44}$
$\displaystyle\quad+\frac{179r}{11}-\frac{31k^{2}}{396}-\frac{31kb}{198}-\frac{62}{11}-\frac{31b^{2}}{176}$
$\displaystyle<\frac{k^{2}}{20}+\frac{kb}{10}+\frac{b^{2}}{20}+\frac{12k}{5}+\frac{12b}{5}+\frac{357}{11}$
$\displaystyle\quad+\frac{1319k}{396}+\frac{181b}{44}-\frac{31k^{2}}{396}-\frac{31kb}{198}-\frac{62}{11}-\frac{31b^{2}}{176}$
$\displaystyle=-\frac{14k^{2}}{495}-\frac{28kb}{495}-\frac{111b^{2}}{880}+\frac{11347k}{1980}+\frac{1433b}{220}$
$\displaystyle\quad+\frac{295}{11}.$

The derivative function of
$-\frac{14k^{2}}{495}+\frac{11347k}{1980}+\frac{295}{11}$ is
$-\frac{28k}{495}+\frac{11347}{1980}$, and thus its maximum point is
$k=\frac{11347}{1980}\cdot\frac{495}{28}<102$. Therefore, the function is
decreasing when $k\geq 208$, and, in this case,

$\displaystyle A(I)-\mathrm{LB}_{2}-\frac{31}{22}\mathrm{LB}_{1}$
$\displaystyle<-\frac{14k^{2}}{495}-\frac{28kb}{495}-\frac{111b^{2}}{880}+\frac{11347k}{1980}+\frac{1433b}{220}$
$\displaystyle\quad+\frac{295}{11}$ $\displaystyle\leq-\frac{14\cdot
208^{2}}{495}-\frac{28\cdot 208b}{495}-\frac{111b^{2}}{880}+\frac{11347\cdot
208}{1980}$ $\displaystyle\quad+\frac{1433b}{220}+\frac{295}{11}$
$\displaystyle\leq-\frac{2377}{495}-\frac{10399b}{1980}-\frac{111b^{2}}{800}<0.$

Similarly, the derivative function of
$-\frac{111b^{2}}{880}+\frac{1433b}{220}+\frac{295}{11}$ is
$-\frac{111b}{440}+\frac{1433}{220}$ and so its maximum point is
$b=\frac{1433}{220}\cdot\frac{440}{111}<26$. Therefore, the function is
decreasing when $b\geq 102$, and in this case

$\displaystyle A(I)-\mathrm{LB}_{2}-\frac{31}{22}\mathrm{LB}_{1}$
$\displaystyle<-\frac{14k^{2}}{495}-\frac{28kb}{495}-\frac{111b^{2}}{880}+\frac{11347k}{1980}+\frac{1433b}{220}$
$\displaystyle\quad+\frac{295}{11}$
$\displaystyle\leq-\frac{14k^{2}}{495}-\frac{28\cdot 102k}{495}-\frac{111\cdot
102^{2}}{880}+\frac{11347k}{1980}$ $\displaystyle\quad+\frac{1433\cdot
102}{220}+\frac{295}{11}$
$\displaystyle\leq-\frac{27329}{44}-\frac{7k}{180}-\frac{14k^{2}}{495}<0.$

Thus, if $k\geq 208$ or $b\geq 102$, then
$A(I)-\mathrm{LB}_{2}-\frac{31}{22}\mathrm{LB}_{1}<0$. ∎

Since $n\geq 266730$ and $n=s+k+b$, if $k<208$ and $b<102$, then

$s\geq 266730-208-102=266420.$

Therefore, $s\geq 266420$ is the complementary case to the cases analyzed in
Lemma 4.

######  Lemma 5.

If $s\geq 266420$, then $A(I)-\mathrm{LB}_{2}-\frac{31}{22}\mathrm{LB}_{1}<0$.

###### Proof.

By Lemma 3 and the upper bounds on $k$ and $b$ in this case,

$\displaystyle A(I)-\mathrm{LB}_{2}-\frac{31}{22}\mathrm{LB}_{1}$
$\displaystyle\leq-\frac{9}{22}R+\frac{13r(k+b)}{9}+\frac{1319k}{396}$
$\displaystyle\quad+\frac{181b}{44}+\frac{403r}{22}-\frac{31k^{2}}{396}-\frac{31kb}{198}-\frac{62}{11}-\frac{31b^{2}}{176}$
$\displaystyle\leq-\frac{9}{22}R+\frac{13r(208+102)}{9}+\frac{1319\cdot
208}{396}$ $\displaystyle\quad+\frac{181\cdot 102}{44}+\frac{403r}{22}$
$\displaystyle\leq-\frac{9}{22}R+\frac{92287r}{198}+\frac{220255}{198}$
$\displaystyle<-\frac{9}{22}R+467r+1113.$

We first consider the case where $r\geq 231$. As seen in the proof of Lemma 4,
$\frac{9}{22}R\geq\frac{45r(r+1)}{22}$. Therefore,

$\displaystyle A(I)-\mathrm{LB}_{2}-\frac{31}{22}\mathrm{LB}_{1}$
$\displaystyle<-\frac{45r(r+1)}{22}+467r+1113$
$\displaystyle<-\frac{45r^{2}}{22}+467r+1113.$

The derivative function of $-\frac{45r^{2}}{22}+467r+1113$ is
$-\frac{45r}{11}+467$ and thus its maximum point is $r=\frac{467\cdot
11}{45}<115$. Thus, the function is decreasing when $r\geq 231$, and, in that
case,

$\displaystyle A(I)-\mathrm{LB}_{2}-\frac{31}{22}\mathrm{LB}_{1}$
$\displaystyle<-\frac{45r^{2}}{22}+467r+1113$ $\displaystyle\leq-\frac{45\cdot
231^{2}}{22}+467\cdot 231+1113<0.$

If $r<231$, then we recall that

$\displaystyle A(I)-\mathrm{LB}_{2}-\frac{31}{22}\mathrm{LB}_{1}$
$\displaystyle<-\frac{9}{22}R+467r+1113$
$\displaystyle\leq-\frac{9}{22}R+467\cdot 231+1113$
$\displaystyle\leq-\frac{9}{22}R+108990.$

Since $s=\sum_{i=1}^{r}|G_{i}|+|G^{S}_{r+1}|$,

$\frac{9}{22}R=\sum_{i=1}^{r}\frac{9}{22}i|G_{i}|+\frac{9(r+1)}{22}|G^{S}_{r+1}|\geq\frac{9s}{22},$

and therefore, if $s\geq 266420$, then

$\displaystyle A(I)-\mathrm{LB}_{2}-\frac{31}{22}\mathrm{LB}_{1}$
$\displaystyle<-\frac{9}{22}R+108990$ $\displaystyle\leq-\frac{9\cdot
266420}{22}+108990$ $\displaystyle=0,$

and the result follows. ∎

Lemmas 4 and 5 show that $A(I)-\frac{53}{22}\mathrm{OPT}(I)<0$ when $n\geq
266730$, and thus the algorithm is a $\frac{53}{22}$-approximation. Without
the assumption on the lower bound on$n$, we still have the following
corollary.

######  Corollary 1.

For any value of $n$, $A(I)<\frac{53}{22}\mathrm{OPT}(I)+27769$.

###### Proof.

Since

$A(I)-\mathrm{LB}_{2}-\frac{31}{22}\mathrm{LB}_{1}<-\frac{45r^{2}}{22}+467r+1113$

and the maximum point of the function is$r=\frac{467\cdot 11}{45}$, we have
that

$\displaystyle A(I)-\mathrm{LB}_{2}-\frac{31}{22}\mathrm{LB}_{1}$
$\displaystyle<-\frac{45r^{2}}{22}+467r+1113$
$\displaystyle\leq-\frac{45}{22}\cdot\left(\frac{467\cdot
11}{45}\right)^{2}+467\cdot\frac{467\cdot 11}{45}+1113$ $\displaystyle<27769,$

and thus $A(I)<\frac{53}{22}\mathrm{OPT}(I)+27769$. ∎

##  4 PTAS

We now present a PTAS for SMSBPP. The idea of the algorithm is similar to the
PTAS for MSBPP presented by [5].

Let $\varepsilon$ be such that $1/\varepsilon$ is an integer and
${\varepsilon\leq 1/4}$. We assume $n\geq 1/\varepsilon^{3}$. Our algorithm
classifies items as small, medium or large such that at least
$1/\varepsilon^{6}$ small items can be packed in the area occupied by a single
large item. We also define medium items such that they are few compared to the
total amount of items in the instance, and that their total area is also small
compared to the total area of all items.

We round up the sizes of the large items and find an optimal packing for these
items in polynomial time, find an unfeasible solution for the small items with
value no greater than the value of an optimal solution for these items, then
combine the two packings into a feasible packing without increasing the value
of the solution by much. Then, we pack the medium items at the end, which will
also not impact the value of the solution much, given how they are chosen.

We now define the medium items. Let
$M_{i}=\\{j:s_{j}\in[\varepsilon^{(3/\varepsilon)(i+1)},\varepsilon^{(3/\varepsilon)i})\\}$
for $i=1,\dots,1/\varepsilon^{3}$. This defines $1/\varepsilon^{3}$ disjunct
subsets of the items in an instance and, therefore, there is at least one
value of $i$ for which $|M_{i}|\leq\varepsilon^{3}n$. For one such value of
$i$, let
$M_{i\ell}=\\{j\in|M_{i}|:s_{j}\in[\varepsilon^{(3/\varepsilon)i+3(\ell+1)},\varepsilon^{(3/\varepsilon)i+3\ell})\\}$
for$\ell=0,\dots,\frac{1}{\varepsilon}-1$. Again, there is at least one value
of $\ell$ for which $\mathrm{AREA}(M_{i\ell})\leq\varepsilon\mathrm{AREA}(I)$.
Let$M=M_{i\ell}$, and, for ease of notation, let$p=(3/\varepsilon)i+3\ell$. We
define the items in $M$ as medium items, the items larger than the medium
items, that is, of size at least $\varepsilon^{p}$, as large items (denoted by
$L$), and the items smaller than the medium items, that is, of size less than
$\varepsilon^{p+3}$, as small items (denoted by $S$).

###  4.1 Small items

We define a Next Fit Increasing Height (NFIH) heuristic to pack the small
items. It is similar to NFDH, however items are ordered in non-decreasing
order of size, and the height of a level is defined as the height of the last
item packed in it. When no more levels can be opened in a bin, items are
packed above the bin, making the solution unfeasible. A new bin is only opened
once $4$ levels have been packed above the current bin. We consider that the
cost of items above a bin is still the index of that bin. Let $Q_{j}$ be the
set of items packed inside bin $B_{j}$ and above it. Also, let $Q$ be the
unfeasible packing done by NFIH, and $V(P)$ the cost of a packing $P$.

(0,0) rectangle (4,4);

[draw=black, fill=lightgray] (0, 0.6-0.1) rectangle (3.9, 3.6-0.1);
[draw=black, fill=lightgray] (0, 3.6-0.1) rectangle (3.6, 3.9-0.1); (0.3,
0.6-0.1) – (0.3, 3.9-0.1); ıin 2, …, 12 (0, 0.3*ı-0.1) – (3.9, 0.3*ı-0.1);
[dashed] (3.9, 0.3*ı-0.1) – (4, 0.3*ı-0.1); (0.3*ı, 0.6-0.1) – (0.3*ı,
3.9-0.1); [draw=black, fill=lightgray] (0,0) rectangle (3.6, 0.15); ıin 1, …,
24 (0.15*ı, 0) – (0.15*ı, 0.15); [draw=black, fill=lightgray] (3.6, 0)
rectangle (3.8, 0.2); [draw=black, fill=lightgray] (0, 0.2) rectangle (3.35,
0.41); ıin 1, …, 15 (0.21*ı, 0.2) – (0.21*ı, 0.41); [draw=black,
fill=lightgray] (3.35, 0.2) rectangle (3.65, 0.5); [draw=black,
fill=lightgray] (3.65, 0.2) rectangle (3.95, 0.5);

(3.8, 0.2) – (4, 0.2); [dashed] (3.6, 3.8) – (4, 3.8);

(-0.2, 4) – (-0.2, 4.5); (-0.3, 4) – (-0.1, 4); (-0.3, 4.5) – (-0.1, 4.5);
(-0.5, 4.25) node $\delta$;

(4.2, 4) – (4.2, 4.6); (4.3, 4) – (4.1, 4); (4.3, 4.6) – (4.1, 4.6); (4.5,
4.3) node $\delta^{\prime}$;

(-0.2, 0.2) – (-0.2, 0.4); (-0.3, 0.2) – (-0.1, 0.2); (-0.3, 0.4) – (-0.1,
0.4); (-0.8, 0.3) node $\geq H_{1}$;

(4.2, 0.2) – (4.2, 0.5); (4.1, 0.2) – (4.3, 0.2); (4.1, 0.5) – (4.3, 0.5);
(4.6, 0.35) node $H_{2}$;

[draw=black, fill=lightgray] (0, 4) rectangle (3, 4.5); ıin 1,…,6 (0.5*ı, 4) –
(0.5*ı, 4.5); [draw=black, fill=lightgray] (3, 4) rectangle (3.6, 4.6);
[draw=black, fill=lightgray] (0, 4.6) rectangle (0.6*6, 5.2); [draw=black,
fill=lightgray] (0, 5.2) rectangle (0.6*6, 5.8); [draw=black, fill=lightgray]
(0, 5.8) rectangle (0.7*5, 6.5); [dashed] (4, 4) – (4, 6.5); [dashed] (0, 4.6)
– (4, 4.6); [dashed] (0, 5.2) – (4, 5.2); [dashed] (0, 5.8) – (4, 5.8);
[dashed] (0, 6.5) – (4, 6.5); [dashed] (0, 4) – (0, 6.5);

ıin 1,…,6 (0.6*ı, 4.6) – (0.6*ı, 5.8);

ıin 1,…,5 (0.7*ı, 5.8) – (0.7*ı, 6.5);

Figure 4: Example of a packing done by NFIH, with four levels packed above a
bin, making the packing unfeasible. The height $H_{i}$ of each level is the
size of the last item packed in it, and, thus, the first item packed in the
level has size at least $H_{i-1}$. The items packed above the bin have size at
least $\delta$ (size of the first item packed above the bin).

Consider any bin of $Q$, except the last one. Let $\delta$ be the size of the
first item of the first level packed above the bin, and
$\delta^{\prime}\geq\delta$ be the size of the last item packed in the same
level, as shown in Figure 4. The size of every item inside the bin is at most
$\delta$ and the size of every item above the bin is at least $\delta$. Let
$H_{i}$ be the height of the $i$-th level in the bin, with ${H_{0}=0}$. The
first item in the $i$-th level has size at least $H_{i-1}$, and, therefore,
the unoccupied area above the items in this level is at most $H_{i}-H_{i-1}$.
Adding this for all levels, we get

$\sum_{i=1}^{t}(H_{i}-H_{i-1})=H_{t}-H_{0}=H_{t}\leq\delta.$

The empty area above the levels inside the bin is less than $\delta^{\prime}$,
as, otherwise, the next level would have been packed within the bin. Also, the
unoccupied width in every level inside the bin is less than $\delta$, as,
otherwise, another item would have been packed in the level. Therefore, the
total unoccupied area inside the bin is less than $2\delta+\delta^{\prime}$.

Each level above the bin has occupied width of at least $1-\varepsilon^{p+3}$,
as, otherwise, another small item would be packed in it. Therefore, the area
occupied in the first level above the bin is at least
$(1-\varepsilon^{p+3})\delta\geq\frac{3}{4}\delta$, since $\varepsilon\leq
1/4$. Similarly, the occupied area in the other levels above the bin is at
least $(1-\varepsilon^{p+3})\delta^{\prime}\geq\frac{3}{4}\delta^{\prime}$.
Let $r$ be the amount of bins used. For $1\leq j<r$,

$\mathrm{AREA}(Q_{j})\geq
1-2\delta-\delta^{\prime}+\frac{3}{4}\delta+\frac{9}{4}\delta^{\prime}\geq 1,$

and, thus, by Lemma 2, we have that

$\mathrm{OPT}(S)\geq\sum_{j=1}^{r}j|Q_{j}|=V(Q).$

We now show how to transform $Q$ into a feasible packing without increasing
the value of the solution by much.

######  Lemma 6.

The unfeasible packing $Q$ can be transformed into a feasible packing $P$ such
that$V(P)\leq(1+\varepsilon)V(Q)$.

###### Proof.

Each level above a bin has height less than $\varepsilon^{p+3}$. Therefore, at
least$1/\varepsilon^{p+3}$ levels fit in a single bin. We divide the bins of
$Q$ into blocks of$\lceil 1/(4\varepsilon^{p+3})\rceil$ bins each (the last
block can have fewer bins), and open a new bin in each block to pack the
levels above the bins of that block. For $k\geq 2$, the new bin of the $k$-th
block is opened at the start of the block, and thus the cost of the items
moved to it do not increase. For the first block, the new bin is opened at the
$1/\varepsilon$-th position.

The items of the first block in bins of index at least $1/\varepsilon$ had
cost of at least $1/\varepsilon$, and this cost increases by $1$ after the
opening of the new bin. Therefore, the increase is by a factor of at most
${1+\varepsilon}$.

The items of the $k$-th block had cost of at least
$\frac{k-1}{4\varepsilon^{p+3}}$, and that cost increases by $k$, since $k$
new bins are opened before them. Since $\varepsilon\leq 1/4$ and, thus, $p\geq
3/\varepsilon\geq 12$, that increase is by a factor of at most

$\left(\frac{k-1}{4\varepsilon^{p+3}}+k\right)\frac{4\varepsilon^{p+3}}{k-1}\leq
1+8\varepsilon^{15}\leq 1+\varepsilon.$

For each bin in which items were packed above the bin, the size of every item
inside the bin is at most $\delta$, while the size of the items above the bin
is at least $\delta$. Therefore, the levels moved to a new bin have at most
$1/\delta$ items each, while the levels that remain inside the bin have at
least $1/\delta$ each. The bin is occupied to at least $1-\varepsilon^{p+3}$
of its height, as, otherwise, another level with only small items would be
packed in it. Thus, at least $(1-\varepsilon^{p+3})/\delta$ levels are packed
inside the bin and the ratio of the number of moved items to the number of
items that remains in the bin is at most

$\frac{4}{\delta}\cdot\frac{\delta^{2}}{1-\varepsilon^{p+3}}=\frac{4\delta}{1-\varepsilon^{p+3}}\leq
8\delta\leq 8\varepsilon^{p+3}<\varepsilon^{2}.$

Therefore, the items above the first $(1/\varepsilon-1)$ bins have the cost
increased by a factor of at most $1/\varepsilon$, and their amount is less
than $\varepsilon^{2}$ of the total of small items, thus the cost of the
solution increases by a factor of at most

$1+\frac{1}{\varepsilon}\varepsilon^{2}=1+\varepsilon,$

and, thus, $V(P)\leq(1+\varepsilon)V(Q)$. ∎

By Lemmas 6 and 2, we have that

$V(P)\leq(1+\varepsilon)\mathrm{OPT}(S).$

###  4.2 Large items

We now describe how to pack the large items. We do a linear grouping of the
large items into $1/\varepsilon^{2p+1}$ groups
$L_{1},\dots,L_{1/\varepsilon^{2p+1}}$ such that
$\lceil\varepsilon^{2p+1}|L|\rceil=|L_{1}|\geq|L_{2}|\geq\cdots\geq|L_{1/\varepsilon^{2p+1}}|\geq|L_{1}|-1$,
with $L_{1}$ receiving the largest items of the instance, $L_{2}$ the next
largest items, and so on. After that, we create a new rounded up instance
$I^{\prime}$ discarding the items in $L_{1}$, and rounding up the sizes of the
remaining large items to the size of the largest item in their respective
group. With this, the amount of distinct item sizes for the large items is
bounded by a constant ($1/\varepsilon^{2p+1}$). Small items remain the same as
in $I$. Since this grouping is very similar to the grouping done in the PTAS
for MSBPP [5], the following lemma still applies.

######  Lemma 7 (Epstein et al., 2018).

A packing $P^{\prime}$ of instance $I^{\prime}$ can be transformed into a
packing $P$ of instance $I$ such that
$V(P)\leq(1+13\varepsilon)V(P^{\prime})$.

Therefore, we focus on finding a packing for $I^{\prime}$ first. Let
$L^{\prime}$ be the large items in $I^{\prime}$. Because the amount of
distinct item sizes in $L^{\prime}$ is bounded by a constant, it is possible
to enumerate all the possible partitions of items and test if they’re a
feasible packing in polynomial time [1]. With this, we can obtain an optimal
packing for $L^{\prime}$ in polynomial time. Let $B_{L_{1}}$ be the first bin
of this packing. We now have two different cases for turning this packing into
a packing of $S\cup L^{\prime}$, depending on the amount of small items in the
instance.

Since small items have area of at most $\varepsilon^{2p+6}$ and large items
have area of at least $\varepsilon^{2p}$, at least

$\frac{\varepsilon^{2p}}{\varepsilon^{2p+6}}=\frac{1}{\varepsilon^{6}}$

small items can be packed in the area occupied by a large item by dividing
this area into a grid of squares with side $\varepsilon^{p+3}$ and packing one
small item into each square. Therefore, if $|S|<|B_{L_{1}}|/\varepsilon^{3}$,
all the small items of the instance can be packed into the areas occupied by
$\lceil\varepsilon^{3}|B_{L1}|\rceil$ large items packed in $B_{L_{1}}$. In
this case, we pack the small items in these areas, overlapping some large
items, and then open a new bin in the $1/\varepsilon$-th position, moving the
overlapped large items to this new bin, as shown in Figure 5. Let $P$ be this
new packing.

[scale=0.5] [draw=black, fill=lightgray] (0,0) rectangle (3,3); (4,0)
rectangle (7,3); (8,0) rectangle (11,3);

(1.5, 0) – (1.5, 3); (0, 1.5) – (3, 1.5); [draw=black, fill=lightgray] (4,0)
rectangle (6,2); [draw=black, fill=lightgray] (8,0) rectangle (10, 2);

(5.3, -0.1) – (5.3, -0.5); (5.7, -0.1) – (5.7, -0.5); (5.3, -0.1) – (5.7,
-0.1); (5.3, -0.5) – (5, -0.5); (5.7, -0.5) – (6, -0.5); (5, -0.5) – (5.5,
-0.9); (6, -0.5) – (5.5, -0.9);

[draw=black, fill=lightgray] (0,-1) rectangle (3,-4); (4,-1) rectangle (7,-4);
(8,-1) rectangle (11,-4); (1.5, -1) – (1.5, -4); (0, -2.5) – (3, -2.5);
[draw=black, fill=lightgray] (4,-2) rectangle (6,-4); [draw=black,
fill=lightgray] (8,-2) rectangle (10, -4); [draw=black, fill=gray] (0, -1)
rectangle (1.5, -2.5); [draw=black, fill=gray] (0, -2.5) rectangle (0.6,
-3.1);

ıin 1, …, 10 (0, -1-0.15*ı) – (1.5, -1-0.15*ı); (0.15*ı, -1) – (0.15*ı, -2.5);
ıin 1, …, 4 (0, -2.5-0.15*ı) – (0.6, -2.5-0.15*ı); (0.15*ı, -2.5) – (0.15*ı,
-3.1);

(5.3, -4.1) – (5.3, -4.5); (5.7, -4.1) – (5.7, -4.5); (5.3, -4.1) – (5.7,
-4.1); (5.3, -4.5) – (5, -4.5); (5.7, -4.5) – (6, -4.5); (5, -4.5) – (5.5,
-4.9); (6, -4.5) – (5.5, -4.9); [draw=white] (-2, -5) – (13, -5); [scale=0.5]
[draw=black, fill=lightgray] (0,-5) rectangle (3,-8); (4,-5) rectangle (7,-8);
(8,-5) rectangle (11,-8); (1.5, -5) – (1.5, -8); (0, -6.5) – (3, -6.5);
[draw=black, fill=lightgray] (4,-6) rectangle (6,-8); [draw=black,
fill=lightgray] (8,-6) rectangle (10, -8); [draw=black, fill=white] (0, -6.5)
rectangle (1.5, -8); [draw=black, fill=lightgray] (0, -6.5) rectangle (0.6,
-7.1);

ıin 1, …, 10 (0, -5-0.15*ı) – (1.5, -5-0.15*ı); (0.15*ı, -5) – (0.15*ı, -6.5);
ıin 1, …, 4 (0, -6.5-0.15*ı) – (0.6, -6.5-0.15*ı); (0.15*ı, -6.5) – (0.15*ı,
-7.1);

(12, -5) rectangle (15, -8); [draw=black, fill=lightgray] (12, -5) rectangle
(13.5, -6.5); [draw=black, fill=lightgray] (12, -6.5) rectangle (13.5, -8);

Figure 5: Example of packing $P$ when $|S|<|B_{L_{1}}|/\varepsilon^{3}$. In
the first step, we have an optimal packing of $L^{\prime}$. In the next step,
small items are packed in the first bin, with the darker region showing the
overlap with the large items already packed there. Finally, in the last step,
the overlapped large items are moved to a new bin, and the packing becomes
feasible.

######  Lemma 8.

$V(P)\leq(1+2\varepsilon)\mathrm{OPT}(I)$.

###### Proof.

As seen in the proof of Lemma 6, by opening a new bin in the
$1/\varepsilon$-th position, items with cost at least $1/\varepsilon$ have
their cost increased by $1$, and thus the increase is by a factor of at most
$1+\varepsilon$.

The cost of each large item moved from $B_{L_{1}}$ to the new bin increases by
$1/\varepsilon-1$. If $\varepsilon^{3}|B_{L1}|\geq 1$, the total increase in
the cost of the solution is at most

$\frac{\lceil\varepsilon^{3}|B_{L1}|\rceil}{\varepsilon}\leq\frac{2\varepsilon^{3}|B_{L1}|}{\varepsilon}\leq
2\varepsilon^{2}|B_{L1}|\leq\varepsilon\mathrm{OPT}(I).$

Otherwise, if $\varepsilon^{3}|B_{L1}|<1$, then $|S|<1/\varepsilon^{6}$, and
thus all the small items are packed overlapping a single large item.
Therefore, only one item is moved to the new bin. Since the amount of items in
the instance is $\mathrm{OPT}(I)\geq n\geq 1/\varepsilon^{3}$, the increase in
the cost of this item is at most $\varepsilon^{2}\mathrm{OPT}(I)$. ∎

We now consider the complementary case where
$|S|\geq|B_{L_{1}}|/\varepsilon^{3}$. In this case, we pack the small items as
seen in Lemma 6, and place the bins of the optimal solution for $L^{\prime}$
at the end of this packing. Again, let $P$ be the new packing obtained.

######  Lemma 9.

$V(P)\leq(1+4\varepsilon)\mathrm{OPT}(S\cup L^{\prime})$.

###### Proof.

Recall that, by Observation 1,

$\mathrm{OPT}(S\cup L^{\prime})\geq\mathrm{OPT}(S)+\mathrm{OPT}(L^{\prime}).$

By Lemma 6, we have that the cost of all small items in $P$ is at most
$(1+\varepsilon)\mathrm{OPT}(S)$.

Every bin in $P$ containing small items has at least
$B_{S}=1/\varepsilon^{2p+6}$ items, except possibly two of them (the last bin
of the packing of small items and the last bin opened to repack the items
packed in an unfeasible way by NFIH), and every bin in $P$ containing large
items has at most $B_{L}=1/\varepsilon^{2p}$. Thus,

$B_{L}=\frac{1}{\varepsilon^{2p}}\cdot\varepsilon^{2p+6}B_{S}=\varepsilon^{6}B_{S},$

that is, the bins with small items at the start of the solution generally have
at least $1/\varepsilon^{6}$ times more items than the bins packing large
items at the end of the solution.

Let $m_{S}$ be the amount of bins used to pack the small items in $P$ and
$m_{L^{\prime}}$ the amount of bins used to pack the items of $L^{\prime}$.
There are at least $\left\lceil\frac{m_{S}}{2}\right\rceil$ bins whose indexes
are at least $\left\lceil\frac{m_{S}+1}{2}\right\rceil$. If $m_{S}\geq 3$,
then

$\displaystyle(1+\varepsilon)\mathrm{OPT}(S)$
$\displaystyle\geq\left(\left\lceil\frac{m_{S}}{2}\right\rceil-2\right)\cdot\left\lceil\frac{m_{S}+1}{2}\right\rceil
B_{S}$
$\displaystyle\geq\left(\left\lceil\frac{m_{S}}{2}\right\rceil-2\right)\frac{m_{S}}{2}B_{S}.$

The cost of every large item increases by $m_{S}$ from the optimal solution
for $L^{\prime}$ to $P$. For the first
$\frac{1}{\varepsilon^{3}}\left(\left\lceil\frac{m_{S}}{2}\right\rceil-2\right)$
bins packing large items, the total increase in the cost of these items is at
most

$\displaystyle\frac{1}{\varepsilon^{3}}\left(\left\lceil\frac{m_{S}}{2}\right\rceil-2\right)m_{S}B_{L}$
$\displaystyle\leq\frac{1}{\varepsilon^{3}}\left(\left\lceil\frac{m_{S}}{2}\right\rceil-2\right)\varepsilon^{6}m_{S}B_{S}$
$\displaystyle\leq 2\varepsilon^{3}(1+\varepsilon)\mathrm{OPT}(S)$
$\displaystyle\leq(2\varepsilon^{3}+2\varepsilon^{4})\mathrm{OPT}(S)\leq\varepsilon\mathrm{OPT}(S).$

The remaining large items have cost at least
$\frac{1}{\varepsilon^{3}}\left(\left\lceil\frac{m_{S}}{2}\right\rceil-1\right)\geq\frac{m_{S}-2}{2\varepsilon^{3}}$
in the optimal solution for $L^{\prime}$, therefore the increase in their cost
in $P$ is by a factor of at most

$1+\frac{2\varepsilon^{3}m_{S}}{m_{S}-2}\leq 1+6\varepsilon^{3}\leq
1+\varepsilon,$

and thus $V(P)$ is at most

$\displaystyle(1+\varepsilon)\mathrm{OPT}(S)+(1+\varepsilon)\mathrm{OPT}(L^{\prime})+\varepsilon\mathrm{OPT}(S)$
$\displaystyle\leq(1+2\varepsilon)\mathrm{OPT}(S\cup L^{\prime}).$

Otherwise, if $m_{S}\leq 3$, then recall that
$\mathrm{OPT}(S)\geq|S|\geq|B_{L1}|/\varepsilon^{3}$, and note that
$|B_{L_{1}}|$ is an upper bound for the amount of items of any bin in $P$
packing large items. For the first $1/\varepsilon$ bins of the optimal
solution for $L^{\prime}$, the increase in the cost of the items packed in
these bins is at most

$\displaystyle\frac{1}{\varepsilon}m_{S}|B_{L1}|$
$\displaystyle\leq\frac{3}{\varepsilon}\varepsilon^{3}|S|\leq\frac{3}{\varepsilon}\varepsilon^{3}\mathrm{OPT}(S)$
$\displaystyle=3\varepsilon^{2}\mathrm{OPT}(S)\leq\varepsilon\mathrm{OPT}(S).$

The remaining large item has cost of at least $1/\varepsilon$ in the optimal
solution for $L^{\prime}$, and so their cost increases by a factor of at most
$1+3\varepsilon$. Thus, $V(P)$ is at most

$\displaystyle(1+\varepsilon)\mathrm{OPT}(S)+(1+3\varepsilon)\mathrm{OPT}(L^{\prime})+\varepsilon\mathrm{OPT}(S)$
$\displaystyle\leq(1+4\varepsilon)\mathrm{OPT}(S\cup L^{\prime}),$

and, therefore, in either case

$V(P)\leq(1+4\varepsilon)\mathrm{OPT}(S\cup L^{\prime}).\qed$

By Lemmas 8 and 9 we have thus that it is possible to pack $S\cup L^{\prime}$
with cost of at most$(1+4\varepsilon)\mathrm{OPT}(I)$.

###  4.3 Medium items

We now show how to pack the medium items. Recall that
$|M|\leq\varepsilon^{3}n$ and
$\mathrm{AREA}(M)\leq\varepsilon\mathrm{AREA}(I)$.

######  Lemma 10.

A packing $P^{\prime}$ of $I\backslash M$ can be transformed into a packing
$P$ of $I$ such that $V(P)\leq(1+7\varepsilon)V(P^{\prime})$.

###### Proof.

Let $m$ be the amount of bins used by $P$. We have that

$\displaystyle m$ $\displaystyle\geq\mathrm{AREA}(I\backslash
M)\geq(1-\varepsilon)\mathrm{AREA}(I)$
$\displaystyle\geq\frac{(1-\varepsilon)\mathrm{AREA}(M)}{\varepsilon}\geq\frac{\mathrm{AREA}(M)}{2\varepsilon}.$

We pack the items of $M$ using NFDH. The size of each medium item is at most
$\varepsilon^{p}\leq\varepsilon^{12}$. Therefore, NFDH leaves at most
$2\varepsilon^{12}$ of area unoccupied per bin packing these items, save for
the last bin [3]. Thus, the amount of items needed to pack all medium items is
at most

$\left\lceil\frac{\mathrm{AREA}(M)}{1-2\varepsilon^{12}}\right\rceil\leq\lceil
2\mathrm{AREA}(M)\rceil\leq\lceil 4\varepsilon m\rceil.$

For $k=1,\dots,1/\varepsilon$, we open four new bins in the $k/\varepsilon$-th
position to pack the medium items, as shown in Figure 6. Every item after the
$k/\varepsilon$-th position has cost at least $k/\varepsilon$ in $P^{\prime}$,
e $4k$ bins are opened before them, therefore their cost increases by a factor
of at most $1+4\varepsilon$.

[scale=0.5] (0,-0.5) rectangle (1.5,-2); (2,-0.5) rectangle (3.5,-2); (4,-0.5)
rectangle (5.5,-2); (6,-0.5) rectangle (7.5,-2); (8,-0.5) rectangle (9.5,-2);
(10,-0.5) rectangle (11.5,-2); (12,-0.5) rectangle (13.5,-2); (14,-0.5)
rectangle (15.5,-2);

(0,0) rectangle (1.5,1.5); (2,0) rectangle (3.5,1.5); (4,0) rectangle
(5.5,1.5); (6,0) rectangle (7.5,1.5); (8,0) rectangle (9.5,1.5); (10,0)
rectangle (11.5,1.5); (12,0) rectangle (13.5,1.5); (14,0) rectangle
(15.5,1.5);

ıin 1, …, 8 (2*ı-2+0.7,-0.3) node$\i$; ıin 9, …, 16 (2*ı-18+0.7,-2.3)
node$\i$; (7.8, -2.6) – (7.8, -3); (8.2, -2.6) – (8.2, -3); (7.8, -2.6) –
(8.2, -2.6); (7.8, -3) – (7.5, -3); (8.2, -3) – (8.5, -3); (7.5, -3) – (8,
-3.4); (8.5, -3) – (8, -3.4);

[draw=white] (0, -3.5) – (1, -3.5); [scale=0.5] (0,-0.5) rectangle (1.5,-2);
(2,-0.5) rectangle (3.5,-2); (4,-0.5) rectangle (5.5,-2); (6,-0.5) rectangle
(7.5,-2); [very thick] (8,-0.5) rectangle (9.5,-2); [very thick] (10,-0.5)
rectangle (11.5,-2); [very thick] (12,-0.5) rectangle (13.5,-2); [very thick]
(14,-0.5) rectangle (15.5,-2);

(0,0) rectangle (1.5,1.5); (2,0) rectangle (3.5,1.5); (4,0) rectangle
(5.5,1.5); (6,0) rectangle (7.5,1.5); [very thick] (8,0) rectangle (9.5,1.5);
[very thick] (10,0) rectangle (11.5,1.5); [very thick] (12,0) rectangle
(13.5,1.5); [very thick] (14,0) rectangle (15.5,1.5);

ıin 1, …, 4 (2*ı-2+0.7,-0.3) node$\i$; ıin 5, …, 8 (2*ı-10+0.7,-2.3) node$\i$;
(8, -3) node$\dots$;

Figure 6: Example of bins of a packing with $\varepsilon=1/4$. The bins with
thick borders in the second step are the bins opened to pack the medium items.

Since we opened $4/\varepsilon$ bins to pack the medium items, the cost of
packing each of them is at most $1/\varepsilon^{2}+4/\varepsilon$. Recall that
the amount of medium items is $|M|\leq\varepsilon^{3}n$ and that
$\varepsilon\leq 1/4$. The total cost of packing all medium items is at most

$\displaystyle\left(\frac{1}{\varepsilon^{2}}+\frac{4}{\varepsilon}\right)\varepsilon^{3}n=(\varepsilon+4\varepsilon^{2})n\leq
2\varepsilon n$
$\displaystyle=\frac{2\varepsilon}{1-\varepsilon^{3}}(1-\varepsilon^{3})n\leq
3(1-\varepsilon^{3})n,$

and if $|M|\leq\varepsilon^{3}n$, then $V(P^{\prime})\geq|I\backslash
M|\geq(1-\varepsilon^{3})n$, and so

$V(P)\leq(1+4\varepsilon)V(P^{\prime})+3\varepsilon
V(P^{\prime})\leq(1+7\varepsilon)V(P^{\prime}),$

thus the result follows. ∎

###  4.4 The PTAS algorithm

With the lemmas in the previous section, we can now present the full algorithm
for our PTAS.

  1. 1.

Classify the items of the instance into small, medium or large, as described
in the beginning of Section 4.

  2. 2.

Create a rounded up instance $I^{\prime}$ as described in Section 4.2, and
find an optimal solution $P_{L^{\prime}}$ for $L^{\prime}$ (the rounded up
large items).

  3. 3.

Transform $P_{L^{\prime}}$ into a packing $P^{\prime}$ for $S\cup L^{\prime}$
in one of the ways described in Section 4.2, depending on the amount of small
items in the instance. By Lemmas 8 and 9,

$V(P^{\prime})\leq(1+4\varepsilon)\mathrm{OPT}(I).$

  4. 4.

Convert $P^{\prime}$ into a packing $P$ for $I\backslash M$, by opening
$|L_{1}|$ new bins to pack the large items discarded in the creation of
$I^{\prime}$. By Lemma 7,

$\displaystyle V(P)$ $\displaystyle\leq(1+13\varepsilon)V(P^{\prime})$
$\displaystyle\leq(1+13\varepsilon)(1+4\varepsilon)\mathrm{OPT}(I)$
$\displaystyle\leq(1+17\varepsilon+52\varepsilon^{2})\mathrm{OPT}(I)$
$\displaystyle\leq(1+30\varepsilon)\mathrm{OPT}(I).$

  5. 5.

Finally, pack the medium items as described in Section 4.3. By Lemma 10, the
final packing has value of at most

$\displaystyle(1+7\varepsilon)(1+30\varepsilon)\mathrm{OPT}(I)$
$\displaystyle=(1+37\varepsilon+210\varepsilon^{2})\mathrm{OPT}(I)$
$\displaystyle\leq(1+90\varepsilon)\mathrm{OPT}(I).$

Therefore, for some $\alpha\leq\varepsilon/90$, the algorithm finds solutions
of value at most $(1+\alpha)\mathrm{OPT}(I)$ in polynomial time, and is thus a
PTAS for SMSBPP.

##  5 Conclusion

In this work we investigated the square min-sum bin packing problem,
presenting an approximation algorithm of simple implementation, constant
approximation ratio, and $O(n\log n)$ time complexity. We have also presented
a PTAS for the problem. There is no proof that the approximation ratio of
$\frac{53}{22}$ for the first algorithm is tight, and a better analysis might
be possible for future work. One possible direction for that is finding better
lower bounds for the value of an optimal solution.

## References

  *   * Bansal . [2006] 2dinapproxBansal, N., Correa, J.R., Kenyon, C. Sviridenko, M.  2006\.  Bin Packing in Multiple Dimensions: Inapproximability Results and Approximation Schemes Bin packing in multiple dimensions: Inapproximability results and approximation schemes.  Mathematics of Operations Research31131-49,  https://doi.org/10.1287/moor.1050.0168
  * Christensen . [2017] approxsurveyChristensen, H.I., Khan, A., Pokutta, S. Tetali, P.  2017\.  Approximation and online algorithms for multidimensional bin packing: A survey Approximation and online algorithms for multidimensional bin packing: A survey.  Computer Science Review2463–79,  https://doi.org/10.1016/j.cosrev.2016.12.001
  * Coffman . [1980] ffdhCoffman, E.G., Jr., Garey, M.R., Johnson, D.S. Tarjan, R.E.  1980\.  Performance Bounds for Level-Oriented Two-Dimensional Packing Algorithms Performance bounds for level-oriented two-dimensional packing algorithms.  SIAM Journal on Computing94808-826,  https://doi.org/10.1137/0209062
  * Eliiyi Eliiyi [2009] applicationsEliiyi, U. Eliiyi, D.T.  2009\.  Applications of bin packing models through the supply chain Applications of bin packing models through the supply chain.  International Journal of Business and Management Studies1111–19,
  * Epstein . [2018] epstein2018Epstein, L., Johnson, D.S. Levin, A.  2018\.  Min-Sum Bin Packing Min-sum bin packing.  Journal of Combinatorial Optimization362508–531,  https://doi.org/10.1007/s10878-018-0310-x
  * Epstein Levin [2007] epstein2007Epstein, L. Levin, A.  2007\.  Minimum weighted sum bin packing Minimum weighted sum bin packing.  International Workshop on Approximation and Online Algorithms International workshop on approximation and online algorithms ( 218–231).
  * Ferreira . [1999] ffdsFerreira, C.E., Miyazawa, F.K. Wakabayashi, Y.  1999\.  Packing squares into squares Packing squares into squares.  Pesquisa Operacional19(2)223-237,
  * Fowler Mönch [2022] batchsurveyFowler, J.W. Mönch, L.  2022\.  A survey of scheduling with parallel batch (p-batch) processing A survey of scheduling with parallel batch (p-batch) processing.  European journal of operational research29811–24,  https://doi.org/10.1016/j.ejor.2021.06.012
  * Graham . [1979] batchnotationGraham, R.L., Lawler, E.L., Lenstra, J.K. Kan, A.R.  1979\.  Optimization and approximation in deterministic sequencing and scheduling: a survey Optimization and approximation in deterministic sequencing and scheduling: a survey.  Annals of discrete mathematics Annals of discrete mathematics ( 5, 287–326).  Elsevier.
  * Moon Moser [1967] squarepackingMoon, J.W. Moser, L.  1967\.  Some packing and covering theorems Some packing and covering theorems.  Colloquium Mathematicum17103-110,
  * Van Stee [2004] square2Van Stee, R.  2004\.  An approximation algorithm for square packing An approximation algorithm for square packing.  Operations Research Letters326535–539,  https://doi.org/10.1016/j.orl.2004.02.003