Geometric packing problems have been investigated for centuries in mathematics.
In contrast, works on sphere packing in the field of approximation algorithms are scarce. Most results are for squares and rectangles, and their $d$-dimensional counterparts.
To help fill this gap, we present a framework that yields approximation schemes for the geometric knapsack problem as well as other packing problems and some generalizations, and that supports not only hyperspheres but also a wide range of shapes for the items and the bins.

Our first result is a  for the hypersphere multiple knapsack problem.
In fact, we can deal with a more generalized version of the problem that contains additional constraints on the items. These constraints, under some conditions, can encompass very common and pertinent constraints such as conflict constraints, multiple-choice constraints, and capacity constraints.

Our second result is a resource augmentation scheme for the multiple knapsack problem for a wide range of convex fat objects, which are not restricted to polygons and polytopes. Examples are ellipsoids, rhombi, hypercubes, hyperspheres under the $L_p$-norm, etc.
Also, for the generalized version of the multiple knapsack problem, our technique still yields a  under resource augmentation for these objects.

Thirdly, we improve the resource augmentation schemes of fat objects to allow rotation on the objects by any angle. This result, in particular, brings something extra to our framework, since most results comprising such general objects are limited to translations.

At last, our framework is able to contemplate other problems such as the cutting stock problem, the minimum-size bin packing problem and the multiple strip packing problem.

§ INTRODUCTION

In general, in packing problems, we have a set of items that must be packed in one or more containers, called bins. In geometric packing problems, the items and the bins are geometric objects, such as squares, (hyper)cubes, (hyper)rectangles and (hyper)spheres. A packing is a non-overlapping arrangement of the items within the bins, and the objective is to optimize some resource, such as minimizing the number or the size of the bins and maximizing the profit associated with the packed items.

Geometric packing problems are classic and relevant problems that have been studied in mathematics for centuries. For instance, in the $17$th century, <cit.> conjectured a bound on the average density of any packing of spheres in the Euclidean space. It was only in $2006$, after centuries, that <cit.> presented a formal proof in the affirmative. More recently, in $2017$, the Fields Medal winner <cit.> gave an optimal packing of equal spheres in the $8$-dimensional space, and together with other authors (<cit.>), extended the result to $24$ dimensions.

From the computational angle, it is known that several geometric packing problems are  <cit.>.
Nevertheless, there are many heuristics and exact algorithms for the problem of maximizing the packing density <cit.>, as well as for the problem of minimizing the size of the container <cit.>.
We refer the reader to the survey of <cit.>.

In the context of approximation algorithms, however, the literature is not so vast and most of the results regard rectangular shapes and $d$-dimensional boxes.
In the bin packing problem, the goal is to pack all items into the minimum number of bins. For rectangular items and bins, the best known result is an asymptotic $1.405$-approximation due to <cit.>, while in the $d$-dimensional context, there is an  for the hypercube bin packing problem, given by <cit.>. For the rectangle strip packing, where the goal is to pack all items into a bin of fixed width and minimum height, <cit.> gave an . We refer the reader to the works of <cit.> and <cit.> for an extensive review. Regarding the knapsack variant, where the items are associated with profits and the objective is to maximize the total profit of the packed items, <cit.> obtained a polynomial-time $(4/3+\eps)$-approximation algorithm when the items are rectangles. In higher dimensions, <cit.> gave a  for the version where the items are restricted to hypercubes. <cit.> studied the knapsack problem for (two-dimensional) convex polygons, presenting a quasi-polynomial-time algorithms.
For the hypersphere bin and strip packing problems, <cit.> gave an  under resource augmentation in only one dimension.
<cit.> derived a  under resource augmentation for the particular case of the circle knapsack problem where the profits of the circles are their respective area (note that, in this case, the objective becomes to maximize the packing density).
For a review of techniques for circle and hypersphere packing, we recommend the survey due to <cit.>.

*Our contribution.
We present a framework that yields approximation schemes for the geometric knapsack problem as well as other packing problems and some generalizations, and that supports a wide range of shapes for the items and the bins.

Our first result is a  for the hypersphere multiple knapsack problem.
In fact, we can deal with a more generalized version of the problem that contains additional constraints on the items, if the number of constraints and associated items are bounded by a constant. These constraints can encompass very common and pertinent constraints such as:

* Conflict constraints: some pairs of items cannot be packed together;

* Multiple-choice constraints: Given a subset $F$ of items, at most one of them can be selected to the solution;

* Capacity constraints: Given weights for each item and a capacity to the knapsack, the sum of the weights of the packed items cannot exceed the capacity.

We observe that it is not expected to be able to handle these constraints if the number of associated variables and constraints is not bounded by a constant, since with these constraints it is possible to model the independent set problem, which does not admit a $(1/n^{1 - \eps})$-approximation for any $\eps > 0$.

Our second result is a resource augmentation scheme for the multiple knapsack problem for a wide range of convex fat objects, which are not restricted to polygons and polytopes. Examples are ellipsoids, rhombi, hypercubes, hyperspheres under the $L_p$-norm, etc.
At a high level, it suffices that the object can be described as a system of a constant number of polynomials; we show that even if the object originally cannot be described this way, we derive an approximate object that can, without occupying much extra space in the knapsack.
We emphasize that all our resource augmentation schemes obtain a solution whose profit is at least the optimum of the non-augmented version.
Also, for the generalized version of the multiple knapsack problem, we obtain a  under resource augmentation even for convex fat objects.

Thirdly, we improve the resource augmentation schemes of fat objects to allow rotation on the objects by any angle. This result, in particular, brings something extra to our framework, since most results comprising such general objects are limited to translations.

Finally, we note that our framework extends to other packing problems, namely the minimum-size bin packing problem, the multiple strip packing problem and the cutting stock problem.

*The technique.
In the following, we summarize the main ideas behind our framework.
We start with the circle knapsack problem.
We first show the existence of a super-optimal and well structured packing. To this end, we follow the ideas employed in the work of <cit.> for partitioning the circles in a way that one subset of circles has negligible total volume (medium items), and the remaining circles ( items) are organized in levels, where circles of a level are much smaller than those of previous levels; then, we use bins of appropriate size for each level.
This strategy gives us flexibility to calibrate the gap of radii among circles of two consecutive levels, as well as the gap of the size between circles and bins of the same level. This, combined with the natural sparsity of circle packing, turns out to be quite convenient to obtain a  from a resource augmentation scheme.

Packing circles, or hyperspheres in general, poses a challenge regarding the realization of a packing.
In $2016$, <cit.> stated as an open question whether there always exists a packing where all the circles assume rational coordinates.
Then, considering that optimal solutions may require irrational coordinates, any algorithm for circle packing (or other geometric packing problems with algebraic constraints) may have to use some resource augmentation, precisely due to the numerical precision of the packing positions.
In the same paper, the authors give an algorithm that, given a set of circles, decides if there is a packing of all the circles in a bin, and in the affirmative case, it returns a packing with rational positions in a bin of slightly increased height.
Their insight was to reduce this problem to the problem of deciding whether a semi-algebraic system is empty.
For that, they render the packing problem as a system of polynomials, whose roots are the coordinates of the circles in the packing (if it exists).
We use the same strategy. Therefore, the resource augmentation present in our  for the multiple knapsack problem is necessary only because of this issue with irrational numbers.

To build our resource augmentation scheme, we use a configuration-based LP to obtain a super-optimal solution of the  circles in a slightly augmented knapsack.
Then, making use the  algorithm we pack a subset of the medium circles whose contribution to the profit of a packing is at least that of the medium items in an optimal solution.
To derive a  for hyperspheres, since the circles of level $1$ onward are really small when compared to items of level $0$, we take advantage of topological properties of circles to guarantee that, for any packing of level $0$, there is a big enough number of free bins left to be used for items of level $1$. With this guarantee, we can simply discard a subset of bins of level $1$ of small profit, thus getting rid of the need for resource augmentation.

*Organization of the text.
In <ref>, we introduce some structural lemmas for the circle packing problem, as well as a generalization of the  algorithm to higher dimensions.
In <ref>, we present a resource augmentation scheme for the circle multiple knapsack problem, which naturally extends to a .
In <ref>, we show extensions of our framework to other packing problems. In particular, in <ref>, we present the more generalized version of the knapsack problem with additional constraints on the items.
In <ref>, we present the generalization of the resource augmentation scheme to convex fat objects in general, as well as the changes introduced to allow rotation on the items.
Finally, in <ref> we offer some
concluding remarks.

§ PRELIMINARIES

Given an integer $n$, we write $[n] = \srange{1}{n}$.
We assume that all objects lie in the Euclidean space.
If $p$ and $q$ are two points in the plane, their Euclidean distance is denoted by $\dist{p}{q}$.
Given a set $\cals = \set{s_1,\ldots,s_n}$ of $n$ circles, we denote the radius and the diameter of each circle $s_i \in \cals$ by $r_i$ and $d_i$, respectively.
For a rectangle $B$ of rational width $w$ and height $h$, we write $B_{w \times h}$ and we call $w \times h$ the size of $B$. When the context is clear, we may omit the size from the notation.
For a two-dimensional geometric object $D$ we denote its area by $\area{D}$, and if $D$ is a set of objects, then $\area{D} = \sum_{A \in D} \area{A}$.
When no ambiguity arises, we denote the area of a circle of radius $r$ simply by $\area{r}$.
When dealing with a more general $d$-dimensional object $D$, we denote by $\vol{D}$ its volume and $\surf{D}$ the area of its surface.
In the same manner as the area, these notations are also used for a set of objects.

§.§ Circle Packing and Gap-Structured Partition

A packing of a set of circles into a bin consists in an attribution of the center position of each circle to coordinates such that no two circles overlap and each circle is entirely contained in the bin.
The study of circle packing in the lens of approximation algorithms began with the work of <cit.> in .
Their work introduced concepts and techniques that served as a baseline for subsequent results in the field.
We summarize some of their results in this section.
They investigated the circle bin packing problem, defined next.

[Circle Bin Packing Problem – ]
Given a set $\cali$ of circles with rational diameters and values $w, h \in \Q_+$, pack all circles of $\cali$ in the minimum number of bins of size $w \times h$.

We denote an instance of the  by $(\cali, w, h)$ and its optimal solution by $\optBP{\cali}{w}{h}$.
Circle packing problems raise an intrinsic issue: It is not known if, for every instance of the problem, there always exists an optimal solution where the center of every circle is given by rational coordinates.
For the , <cit.> handle this issue providing
an algorithm that always produces rational solutions, but in augmented bins.
Briefly, the idea is to formulate the problem as a system of polynomial inequalities where the variables correspond to the center position of the circles.
The set of solutions that satisfy these constraints is a semi-algebraic set in the field of the real numbers, and therefore any algorithm for the more general quantifier elimination problem can be used to decide whether such set is empty.
Using this strategy, we can decide whether a set of circles fit in a bin, even if irrational coordinates were to be necessary.
However, we cannot guarantee a realization of such packing in rational coordinates, since the positions are given by roots of polynomials, which may be irrational numbers.
Trying to adjust them to rational coordinates may cause overlaps with the borders of the bin or among circles, resulting in an approximate packing, which is defined as follows.
For some number $\xi$, we say that an attribution of some circles $\cali$ in coordinates $p_i = (x_i, y_i)$ for each $s_i \in \cali$ into a bin of size $w \times h$ is a $\xi$-packing if no two circles overlap by more than $\xi$ and no circle overlap the bin by more than $\xi$ in any dimension. More formally, in a $\xi$-packing it holds that

p_ip_j    ≥r_i + r_j - ξ≥0           ∀  s_i, s_j ∈, s_i ≠s_j,

r_i - ξ   ≤x_i ≤w - r_i + ξ              ∀  s_i ∈,

r_i - ξ   ≤y_i ≤h - r_i + ξ              ∀  s_i ∈.

<cit.> present a shifting strategy to rearrange the circles within the bin until there is no overlap, resulting in an increase in the height of the bin by a small value.
We state this result in the next lemma.

Given a set of circles $\cali$ with $\size{\cali} = n$, and a $\eps h$-packing of $\cali$ into a bin $B_{w \times h}$ for some $\eps> 0$, we can ﬁnd a packing of $\cali$ into a bin of size $w \times (1 + n\sqrt{6\eps})h$ in linear time.

Using this result alongside an algorithm similar to the one of <cit.>, they obtain a super-optimal solution for the  in augmented bins for the particular case of large circles, i.e, the radius of each circle is greater than a given constant. This is stated next.

Let $(\cali, w, h)$ be an instance of the circle bin packing problem, where $w, h \in \bigO(1)$ and $|\cali| = n$, and such that $\min_{1 \leq i \leq n} r_i \geq \delta$ and $|\srange{r_1}{r_n}| \leq K$, for constants $\delta$ and $K$.
Given a number $\gamma > 0$, there exists an algorithm that produces a packing of $\cali$ into at most $\optBP{\cali}{w}{h}$ bins of size $w \times (1+\gamma)h$, in polynomial time on $n$.

Then, in possession of this result, they derive an  under resource augmentation for any instance of the .
The key idea is to prove that there is a well-behaved structure for the packing of circles that is almost optimal, in the sense that it wastes little area compared to an optimal solution.
Such structure relies on a fastidious partitioning of the instance, which is called a gap-structured partition, and is explained next.

Let $(\cali, w, h)$ be an instance of the  and let $\eps > 0$ be a constant.
We define $\reveps = 1/\eps$.
We partition $\cali$ into groups $G_i = \set{ s_j \in \cali : \eps^{2i} w \geq d_j > \eps^{2(i+1)} w }$, for $i \geq 0$.
Then we partition these groups into sets $H_{\ell} = \bigcup_{i \equiv \ell \pmod{\reveps}}{G_i}$, for $0 \leq \ell < \reveps$.
Now consider a fixed set $H_t$ for some index $0 \leq t < r$. We refer to $H_t$ as the medium items.
By removing the set $H_t$ from the instance, we can arrange the remaining groups into sets of groups such that there is a significant gap on the radii of circles of any two consecutive sets.
For that purpose, we define sets $S_j = \bigcup_{i = t + (j-1)\reveps + 1}^{t + j\reveps - 1} G_i$, for $j \geq 0$.
See <ref> for an illustrative sketch.
We denote by $\struct{\cali}{t} = \cali \setminus H_t = \bigcup_{j \geq 0} S_j$ the level items and say that $H_t, S_0, S_1, \dots$ is a gap-structured partition of $\cali$.
The minimum and maximum radii of $S_j$ are denoted by $\rmin{j}$ and $\rmax{j}$, respectively.
The strategy is to pack each $S_j$ in bins of appropriate dimensions according to the size of the circles.
We set $w_0 = w$, $h_0 = h$, representing the knapsack itself, and for $j \geq 1$, we set $w_j = h_j = \eps^{2(t + (j-1)\reveps) +1} w$.
We say that a grid of size $w_j \times h_j$ over a bin $B$ divides $B$ into a set $\grid{j}{B}$ of square cells of size $w_j \times h_j$.
Additionally, we say that a bin $B'_{w_j \times h_j}$ respects $w \times h$ if $B' \in \grid{j}{B}$.
To avoid verbosity, hereafter we refer to each $j$ as level $j$. Many times throughout the text we refer to circles of $S_j$ and bins of size $w_j \times h_j$ simply as circles and bins of level $j$.

\begin{equation*}
\def\arraystretch{1.4}\arraycolsep=4pt
\begin{array}{rrrrrcl|c}
% \hline
&                &  &  &      &       &         & \textcolor{gray}{H_t}\!\\
S_0\mathclose{:} &                &  & & G_0   & \dots & G_{t-1} & \textcolor{gray}{G_t}\\
S_1\mathclose{:} & G_{t+1}        & G_{t+2}    & \dots & G_r     & \dots  & G_{t+r-1}   & \textcolor{gray}{G_{t+r}}\\
S_2\mathclose{:} & G_{t+r+1}      & G_{t+r+2}  & \dots & G_{2r}  & \dots  & G_{t+2r-1}  & \textcolor{gray}{G_{t+2r}}\\
S_j\mathclose{:} & G_{t+(j-1)r+1} & G_{t+jr+2} & \dots & G_{3r}  & \dots  & G_{t+jr-1}  & \textcolor{gray}{G_{t+jr}}\\
&                & \vdots & &\vdots     &          &             & \;\; \textcolor{gray}{\vdots} \\
\end{array}
\end{equation*}

Sketch to illustrate the partitioning of the original instance.

We highlight two important properties regarding the sets $S_j$, for $j \geq 1$:
$i)$ within the same level, circles are small compared to bins; and
$ii)$ between two consecutive levels $j$ and $j+1$, circles and bins of level $j+1$ are much smaller than circles and bins of level $j$.
This indicates that after packing circles of a level only in bins of that same level, the area left unoccupied can accommodate a great number of circles (and bins) of the subsequent level.
The idea is to recursively use grids to build a packing respecting a certain structure: For each level $j$, circles are packed in bins of their respective levels, over which it is drawn a grid of size $w_{j+1} \times h_{j+1}$; the empty cells of this grid are then used to pack circles of $S_{j+1}$, as illustrated in <ref>.
For clarity, from level $1$ onward, we say subbins instead of just bins.
In the following, we present a formal definition.

cir/.style=draw, circle, minimum width=#1 cm,
gridS2/.style=step=0.25, black!80, ultra thin

[cir=2.5] at (0.0, 0) ;
[cir=2.15] at (2.45, -0.2) ;
[cir=0.5] at ( 0.0, 0.0) ;
[cir=0.4] at ( 0.15, 0.5) ;
[cir=0.4] at ( 0.35, -0.4) ;
[cir=0.4] at ( 0.55, 0.1) ;
[cir=0.4] at ( 0.7, 0.55) ;
[cir=0.5] at ( 1.1, 0.1) ;
[cir=0.4] at ( 0.85, -0.35) ;
[cir=0.5] at ( 1.5, 0.5) ;
[cir=0.4] at ( 1.4, -0.3) ;
[cir=0.5] at ( 1.8, 0) ;
[cir=0.4] at ( 2.1, 0.5) ;
[cir=0.4] at ( 2, -0.5) ;
[cir=0.4] at ( 2.35, -0.05) ;
ıin 0, ..., 6
[shift=(0.45*ı, 0), rotate=45*ı, transform shape]  pic circlesS2set;
[shift=(0.4 + 0.45*ı, -0.4), rotate=45*ı, transform shape]  pic circlesS2set;

[cirS2] ( 0.00, 0.00) circle [radius=0.04cm];
[cirS2] (-0.10, 0.15) circle [radius=0.05cm];
[cirS2] ( 0.12, 0.10) circle [radius=0.035cm];
[cirS2] ( 0.10,-0.12) circle [radius=0.05cm];
[cirS2] (-0.11,-0.11) circle [radius=0.04cm];
[cirS2] (0.05,0.05) + (-0.125,-0.125) circle [radius=0.04cm];
[cirS2] (0.1,0.125) + (-0.125,-0.125) circle [radius=0.04cm];
[cirS2] (0.15,0.05) + (-0.125,-0.125) circle [radius=0.03cm];
[cirS2] (0.03,0.15) + (-0.125,-0.125) circle [radius=0.03cm];
[cirS2] (0.075,0.2) + (-0.125,-0.125) circle [radius=0.03cm];
[cirS2] (0.16,0.2) + (-0.125,-0.125) circle [radius=0.035cm];
[cirS2] (0.175,0.125) + (-0.125,-0.125) circle [radius=0.03cm];

at (-2,9) $S_0$;
(0, 9) pic circlesS0;

at (-2,6.4) $S_1$;
(0, 6.4) pic circlesS1;

at (-2,4.8) $S_2$;
(-0.3, 5) pic circlesS2;

[cir=2.5] at (6.25, 6.25) ;
[cir=2.15] at (7.9, 7.9) ;

[cir=0.5] at (5.25, 8.25) ;
[cir=0.4] at (5.725, 8.2) ;
[cir=0.4] at (5.2, 8.7) ;
[cir=0.5] at (5.65, 8.65) ;

[cir=0.5] at (8.25, 5.25) ;
[cir=0.5] at (8.25, 5.75) ;

ıin 8.50, 8.75
ȷin 5.00, 5.25, ..., 5.75
(ı, ȷ) + (0.125, 0.125) pic packingS2;

[step=1] (5,5) grid (9,9);

[gridS2] (8,5) grid (9,6);
[gridS2] (5,8) grid (6,9);

Illustration of a structured packing.

Consider a set $\cali$ of circles. We say that a packing of $\struct{\cali}{t}$ in a bin $B_{w \times h}$ is a structured packing if the following holds:

* $S_0$ is packed in $B$;

* for every $j \geq 1$, $S_j$ is packed in a subset $D_j \subseteq \grid{j}{B}$ of subbins of size $w_j \times h_j$; and

* for every subbin $D' \in D_j$, $D'$ does not intersect any circle from $S_{\ell}$, for $\ell < j$.

Note that in a structured packing, the subbins that partially intersect a circle of some previous level are not used, and this causes a waste of area. However, such waste is small, as shows the next lemma.

Let $A \subseteq S_j$ be a set of circles packed in a bin $B_{w_j \times h_j}$ and $D \subseteq \grid{j+1}{B}$ be the subset of grid cells of size $w_{j+1} \times h_{j+1}$ intersecting but not entirely contained in circles of $A$. Then $\area{D} \leq 16\eps \area{A}$.

<cit.> show that for any instance $(\cali,w,h)$ of the  and a gap-structured partition of $\cali$, there is a structured packing of $\struct{\cali}{t}$ using only a small amount of extra area.

Let $(\cali, w, h)$ be an instance of the  and let $H,S_0,S_1,\ldots$ be a gap-structured partition of $\cali$.
There exists a structured packing of $\cali\setminus H$ into a set of bins $D$ that respect $w \times h$ such that $\area{D} \leq (1 + 44\eps) \opt_{w \times h}^{\bp}(\cali) wh$.

§.§ The Next Fit Decreasing Height Algorithm

The next fit decreasing height () procedure is an algorithm originally proposed for the two-dimensional strip packing problem of rectangles and introduced by <cit.>.
It consists in first sorting the rectangles in non-increasing order of height, and then packing the items in a shelf-like manner:
Starting from the bottom left of the bin, the items are sequentially positioned adjacent to one another until the subsequent item would overlap the right border of the bin.
At this point, the algorithm defines a new level at the top of the tallest item in the current level and continues placing the items next to each other in this new level.
<ref> illustrates this procedure for squares.

code =

[fill=gray!20] (0,0) rectangle (#1, #1);
(-left)  at ( 0,0) ;
(-right) at (#1,0) ;

code =

(c1) at (0,0)  square=[1] ;
ıin 2, ...,
ȷint(ı- 1)
(cı) at ($(c\j-right)$) square=;

(-end) at (c-right |- 0,0) ;

(0,6) – (0,0) – (9.4,0) – (9.4,6);

at (0,0)    listsquare=2, 2, 1.9, 1.75, 1.6 ;
at (0,2)    listsquare=1.5, 1.4, 1.3, 1.3, 1.2, 1.2, 1.2 ;
at (0,3.5)  listsquare=1.2, 1.1, 1, 0.9, 0.8, 0.8, 0.7, 0.7, 0.65, 0.6, 0.6 ;
at (0,4.7)  listsquare=0.55, 0.5, 0.5, 0.45, 0.45, 0.45, 0.4, 0.4, 0.35, 0.35, 0.35, 0.35, 0.3, 0.3, 0.3, 0.25, 0.25, 0.25, 0.2, 0.2, 0.2, 0.15, 0.15, 0.1, 0.1, 0.1 ;

applied for a set of squares.

The  algorithm has been used in several packing problems to obtain approximation algorithms due to its properties regarding the packing density.
Because of that, a generalized version of  for multiple dimensions, mainly for hypercubes, has been extensively investigated in the literature, with first analyses dating back to  <cit.>.
The $d$-dimensional  algorithm for hypercubes can be explained in a recursive manner.
Electing a dimension as the height, we start with a base on the bottom of the bin in this dimension,
and consider the projection of the hypercubes and the bin in the remaining $d-1$ dimensions.
Then we pack the largest amount of hypercubes using the $(d-1)$-dimensional version of .
At last, we pack such items in the base and shift the base to the top of the largest packed hypercube, repeating the process for the remaining items.

<cit.> showed a sufficient condition for the  algorithm to be able to pack a set of hypercubes in a bin, based on their sizes.

Let $\cali$ be a list of $d$-dimensional hypercubes, with side lengths at most $\delta$. The  algorithm can pack $\cali$ in an hypercuboidal bin of size $\ell_1 \times \ell_2 \times \dots \times \ell_d$ whenever

\begin{equation*}
\vol{\cali} \leq \delta^d + \prod_{i=1}^d(\ell_i - \delta).
\end{equation*}

By isolating $\ell_d$ in this theorem, we obtain the following:

Let $\cali$ be a list of $d$-dimensional hypercubes, with side lengths at most $\delta$. The  algorithm can pack $\cali$ in a hypercuboidal bin of size $\ell_1 \times \ell_2 \times \dots \times \ell_d$ whenever

\begin{equation*}
\ell_d \geq \frac{ \vol{\cali} - \delta^d }{ \prod_{i=1}^{d-1}(\ell_i - \delta) } + \delta.
\end{equation*}

<cit.> gave an efficiency guarantee of the  algorithm based on the surface area.

Let $S$ be a set of hypercubes with side length at most $\delta$ and a hypercuboidal bin $B$. The  algorithm either packs all the items of $S$ in $B$ or the total volume left empty inside $B$ is at most $\delta\,\surf{B} / 2$.

Although these efficiency guarantees of  are restricted to hypercubes, the algorithm can still be useful for packing other geometric forms, such as hyperspheres.
In order to use the  algorithm for these shapes, we wrap the objects in hypercubes.
Given a geometric object $C$, we denote by $\squarehull{C}$ the smallest hypercube that contains $C$.
We extend this notation for sets, i.e., if $S$ is a set of geometric objects, we define $\squarehull{S} = \set{\squarehull{x} : x \in S}$.
We particularly use this strategy in <ref> when packing small circles, in which the wasted area by encapsulating the circles into squares is small.
To aid in this process, we state next a helper corollary that provides a bound on the height of a bin to pack small squares.

Given $\eps \leq 1/4$ and $w, h, \alpha, \beta \in \Q_+$ with $w \leq h$,
let $\cali$ be a set of squares such that $\area{\cali} \leq \alpha \eps w h$ and whose side lengths are bounded from above by $\bar{s} = \beta \eps^2 w$.
The  algorithm packs $\cali$ in a bin of size $w \times h'$ with

\begin{equation*}
h' \leq \frac{64\alpha + 16\beta - \beta^2}{64 - 4\beta} \eps h.
\end{equation*}

From <ref>,  is able to pack $\cali$ using height

\begin{align*}
h' &= \frac{ \area{\cali} - \bar{s}^2 }{ w - \bar{s} } + \bar{s} \\
&\leq \frac{ \area{\cali} }{ w - \bar{s} } + \bar{s} \\
&\leq \frac{ \alpha \eps wh }{ w - \beta \eps^2 w} + \beta \eps^2 w \\
&= \frac{\alpha}{1 - \beta \eps^2} \eps h + \beta \eps^2 w.
\end{align*}

Since $\eps \leq 1/4$ and $w \leq h$, we have that $\displaystyle{} \frac{\alpha}{1 - \beta \eps^2} \leq \frac{16 \alpha}{16 - \beta}$ and $\displaystyle{} \beta \eps^2 w \leq \frac{\beta}{4} \eps h$. By replacing these factors, we obtain that

\begin{align*}
h' &\leq \frac{16 \alpha}{16 - \beta} \eps h + \frac{\beta}{4} \eps h \\
&= \frac{64\alpha + 16\beta - \beta^2}{64 - 4\beta} \eps h.
\end{align*}

§ THE CIRCLE MULTIPLE KNAPSACK PROBLEM

Formally, an instance of the circle multiple knapsack problem () is defined as a tuple $(\cali, w, h, p, m)$ where ${w, h \in \Q_+}$ are the dimensions of the knapsacks, with $w \leq h$, ${\cali = \srange{s_1,}{s_n}}$ is a set of $n$ circles, each circle $s_i \in \cali$ with diameter $d_i \in \Q_+$ and $d_i \leq w$, ${p \from \cali \to \Q_+}$ is a function of profit on the circles, and $m \in \Z_+$ is the number of available knapsacks.
We denote the profit of a circle $s_i$ as $\profit{i}$.
If $A$ is a set of circles, we say its profit is $\profits{A} = \sum_{s_i \in A} \profit{i}$.
The objective of the  is to find a packing of a subset $I \subseteq \cali$ of circles in at most $m$ knapsacks of size $w \times h$, maximizing $\profits{I}$.
We denote the optimal value of  for instance $(\cali, w, h, p, m)$ by $\optMKP{\cali}{m}{w}{h}$.
The circle knapsack problem () is the particular case of  where $m = 1$.
We denote an instance of the  by the tuple $(\cali, w, h, p)$ and its optimal value by $\optKP{\cali}{w}{h}$.

In this section, we first describe a resource augmentation scheme for the , i.e., given an instance $(\cali, w, h, p)$ and a constant $\eps > 0$, we give a polynomial-time algorithm that finds a packing of a subset $I \subseteq \cali$ into a knapsack of size $w \times (1 + \eps) h$ such that $p(I) \geq \optKP{\cali}{w}{h}$.
Moreover, we first assume that $w$ and $h$ are bounded by constants, and later we extend the result for the  and for knapsacks of unconstrained size.
Hereafter, we define $\reveps = 1/\eps$ and without loss of generality we assume that $\eps \leq 1/4$ and that $\reveps$ and $h\reveps/w$ are integers.

§.§ Structural Theorem for the

We intend to make use of the structured packing properties of <cit.>.
For that, we first need to show that there actually exists a super-optimal structured packing in an augmented knapsack.
Then consider the gap-structured partition procedure as in <ref>.
We show that we can make all circles of a packing respect a structured packing by increasing the height of the knapsack by a small factor.

Let $(\cali,w,h,p)$ be an instance of the .
For any subset $I \subseteq \cali$ that fits in the knapsack, there is a structured packing of $I$ in an augmented knapsack of size $w \times (1 + 192\eps)h$.

Let $I$ be the set of circles packed in a feasible solution of the  instance.
First, we obtain a bound on the total area that is required to guarantee the existence of a structured packing of $I$.
To achieve this, we will make use of <ref> to get such a bound for the circles of $I$ except for a set of medium items $H$, and then apply this procedure recursively to $H$ in a smaller bin, until all items are considered.

For that, let $\bar{h}_0 = h$ and $\bar{h}_j = 3 \eps \bar{h}_{j-1} = (3 \eps)^j h$ for $j \geq 1$.
We also denote $I$ by $\medium{0}$, and for $j \geq 1$, let $\medium{j}$ be a set of medium items originated from a gap-structured partition of $\medium{j-1}$ with regard to a bin of size $w \times \bar{h}_{j-1}$, in such a way that $\area{\medium{j}} \leq 2 \eps \area{ \medium{j-1} }$ and $t_j \geq 1$.
We show next that for any $j \geq 0$, there exists a structured packing of $\medium{j} \setminus \medium{j+1}$ into a set of bins $D_j$ that respect $w \times \bar{h}_j$ such that $\area{D_j} \leq (1 + 44\eps) w \bar{h}_j$.

Since $\medium{0} = I$, the result follows directly from <ref> for $j = 0$, so now consider some $j \geq 1$.
First, it can be shown by induction that $\area{\medium{j}} \leq 2 \eps w \bar{h}_{j-1}$, as follows.
For $j = 1$ we have that $\area{\medium{1}} \leq 2 \eps \area{\medium{0}} \leq 2 \eps w \bar{h}_0$.
Now assuming that it holds for $j-1$, for $j$ we obtain that

\begin{equation*}
\area{\medium{j}} \leq 2 \eps \area{\medium{j-1}} \leq 2\eps (2\eps w \bar{h}_{j-2}) \leq 2\eps w (3 \eps \bar{h}_{j-2}) = 2 \eps w \bar{h}_{j-1}.
\end{equation*}

In addition, since $t_j \geq 1$, we know that the diameter of the circles in $\medium{j}$ are bounded from above by $\eps^2 w$.
Hence, since when wrapping a circle in a square its area increases by $4/\pi$,
we have that $\area{\squarehull{\medium{j}{}}} \leq \frac{8}{\pi} \eps w \bar{h}_{j-1}$, and their side lengths are at most $\eps^2 w$. Then, from <ref> we conclude that  is able to pack $\squarehull{\medium{j}{}}$ in a bin of size $w \times h'$ with

\begin{equation*}
h' \leq \frac{ 64 \cdot \frac{8}{\pi} + 16 - 1 }{64 - 4} \eps \bar{h}_{j-1} \leq 3 \eps \bar{h}_{j-1} = \bar{h}_j.
\end{equation*}

Thus, $\medium{j}$ fits in a bin of size $w \times \bar{h}_j$, which implies that
$\optBP{\medium{j}}{w}{\bar{h}_j} = 1$.
Therefore, from <ref> we conclude that there is a structured packing of $\medium{j} \setminus \medium{j+1}$ into bins $D_j$ that respect $w \times \bar{h}_j$ and such that $\area{D_j} \leq (1 + 44\eps) \optBP{\medium{j}}{w}{\bar{h}_j} w \bar{h}_j = (1 + 44\eps) w \bar{h}_j$.

Note that since $\area{\medium{j}} < \area{\medium{j-1}}$, at most $n$ iterations are required to consider all circles of $I$. Therefore, there exists a structured packing of all circles of $I$ into the set of bins $\cald := \bigcup_{j=0}^{n-1} D_j$ that respect $w \times h$, and whose area is given by

\begin{align*}
\area{\cald} &= \sum_{j=0}^{n-1} \area{D_j} \\
&\leq (1 + 44\eps) w \sum_{j=0}^{n-1} \bar{h}_j \\
&\leq (1 + 44\eps) w h \sum_{j=0}^{\infty} (3 \eps)^j \\
&= (1 + 44\eps) w h \paren*{ 1 + \frac{3\eps}{1 - 3\eps} }. \\
\end{align*}

From the assumption that $\eps \leq 1/4$, we have that $1/(1 - 3\eps) \leq 4$, and therefore

\begin{align*}
\area{\cald} &\leq (1 + 44\eps) wh (1 + 12\eps) \\
&= (1 + 56\eps + 528\eps^2) wh \\
&\leq (1 + 188\eps) wh,
\end{align*}

for $\eps \leq 1/4$.

At last, given the bound on the area of $\cald$, it remains to obtain a bound on the height of the augmented knapsack that is sufficient to accommodate a structured packing of $\cald$.
For that, we can simply use , since the packing of $\cald$ obtained by the  algorithm naturally results in a structured packing.
Denoting by $\cald'$ the bins of $\cald$ of level $1$ onward, we have that $\area{\cald'} \leq 188\eps w h$ and letting $t$ be the smallest $t_j$ from the sets $\medium{j}$ that originated the sets $D_j$, we have that $t \geq 1$ and thus the side length of the bins of $\cald'$ is bounded from above by $\eps^{2t + 1} w \leq \eps^3 w \leq \frac{1}{4} \eps^2 w$.
From <ref> we have that  packs $\cald'$ in a bin of size $w \times \Hat{h}$ with

\begin{equation*}
\Hat{h} \leq \frac{ 64 \cdot 188 + 16/4 - 1/16 }{ 64 - 1 } \eps h \leq 192 \eps h.
\end{equation*}

Hence, we conclude that a knapsack of size $w \times (1 + 192\eps) h$ is sufficiently big to accommodate a structured packing of $\cald$, and consequently of $I$.

We use the gap-structured partitioning procedure presented in <ref>,
but we employ a different scaling on the size of the items and subbins, as follows.
We partition $\cali$ into groups $G_i = \set{ s_j \in \cali : \eps^{\reveps i} w \geq d_j > \eps^{\reveps(i+1)} w }$, for $i \geq 0$.
The next steps remain the same: The partitioning of the groups $G_i$ into sets $H_{\ell} = \bigcup_{i \equiv \ell \pmod{\reveps}}{G_i}$; the selection of a set of medium items $H_t$; and the regrouping of $\cali \setminus H_t$ into levels $S_j = \bigcup_{i = t + (j-1)\reveps + 1}^{t + j\reveps - 1} G_i$.
Now regarding the size of the subbins of each level, we set $w_0 = w$, $h_0 = h$, and for $j \geq 1$, we set $w_j = h_j = \eps^{\reveps(t + (j-1)\reveps) + \reveps - 1} w$.

For our algorithm, we choose the medium items as follows.
Let $I^* \subseteq \cali$ be the set of circles of an optimal solution.
For some $1 \leq t < \reveps$, there must be a set $H_t$ such that $\area{H_t \cap I^*} \leq \frac{1}{(\reveps - 1)} w h \leq 2 \eps w h$.
Thus, we fix such index $t$ and handle the medium items $H_t$ separately, by packing a high-profit subset of $H_t$ in a strip of small height.
Then, we exploit the properties of the gap-structured partition to obtain a good packing of the  items, $\struct{\cali}{t}$.
Despite the change in the scaling, the result of <ref> remains valid, since the change only makes the size of the subbins smaller.

§.§ Packing of the Medium Items

Note that by our choice of $H_t$, we have no information about the profit arising from $H_t$ in some optimal solution $I^*$, i.e., $\profits{H_t \cap I^*}$.
On the other hand, we know that the area of the medium items in an optimal solution is small, more specifically, $\area{H_t \cap I^*} \leq 2\eps w h$, and the medium items themselves are small, that is, their diameter is at most $\eps^\reveps w$, from the fact that $t \geq 1$.
We use these facts to obtain a packing of a subset of $H_t$ in a strip of small height ($\bigO(\eps) h$), and with profit at least $\profits{H_t \cap I^*}$.
This is accomplished by <ref>, shown next.

Set $H_t$ of medium items originated from a gap-structured partition, and constant $\eps$.

Packing of a subset of $H_t$ into a bin of size $w \times 8 \eps h$.
Sort $H_t$ in non-increasing order of $p_i / d_i$
Let $B'$ be a bin of size $(1 + \eps) w \times 4 \eps h$
Let $j$ be the largest integer for which  is able to pack the first $j$ items of $\squarehull{H_t}$ in $B'$
$P$ := packing of the first $j$ items of $\squarehull{H_t}$ in $B'$ by
Transform $P$ into a packing in a bin of size $w \times 8 \eps h$

We will show that <ref> actually obtains a high-profit packing of $H_t$.
For that, let us denote by $H_t^* = H_t \cap I^*$ the circles of the medium items that are present in an optimal solution.
We first use the  algorithm to obtain a bound on the height that is necessary to pack $H_t^*$.

The circles of $H_t^*$ fit in a bin of size $w \times 3 \eps h$.

From the facts that $\area{H_t^*} \leq 2\eps wh$ and $t \geq 1$, we have that $\squarehull{{H_t^*}}$ is composed of squares of side length at most $\eps^\reveps w$ and $\area{\squarehull{{H_t^*}}} \leq \frac{8}{\pi} \eps w h$.
From <ref>, the  algorithm would pack $\squarehull{{H_t^*}}$ in a bin of width $w$ and height $h'$ such that

\begin{align*}
h' &= \frac{ \area{\squarehull{{H_t^*}}} }{ w - \eps^\reveps w } + \eps^\reveps w \\
&\leq \frac{8}{\pi} \cdot \frac{\eps w h}{w - \eps^\reveps w} + \eps^\reveps w \\
&= \frac{8}{\pi} \cdot h \paren*{ \frac{\eps}{1 - \eps^\reveps} } + \eps^\reveps w \\
&\leq \paren*{ \frac{8}{\pi} \cdot \frac{\eps}{1 - \eps^\reveps} + \eps^\reveps } h
\end{align*}

from the fact that $w \leq h$. Now, since $\eps \leq 1/4$, we have that $\eps^\reveps \leq \frac{1}{64} \eps$ and $\frac{1}{1 - \eps^\reveps} \leq \frac{256}{255}$. Making these replacements, we obtain that

\begin{equation*}
h' \leq \paren*{ \frac{8}{\pi} \cdot \frac{256}{255} \eps + \frac{1}{64} \eps } h \leq 3\eps h.
\end{equation*}

Therefore, $\squarehull{{H_t^*}}$, and consequently ${H_t^*}$, fits in a bin of size $w \times 3 \eps h$.

Now, in knowledge of this bound, we  proceed to show that the area occupied by the packing obtained in <ref> is at least the one of $\squarehull{{H_t^*}}$, which guarantees a high profit due to the ordering of $H_t$.

<ref> obtains a packing of a subset of $H_t$ whose profit is at least $\profits{H_t^*}$ in a bin of size $w \times 8 \eps h$.

Consider $H_t = (x_1, x_2, \dots)$ ordered in non-increasing order of $\profit{i}/d_i$.
Since we know from <ref> that ${H_t^*}$ fits in a bin of size $w \times 3 \eps h$, we define $B'$ as a slightly bigger bin of size $(1 + \eps) w \times 4 \eps h$.
We define $H_t^k = (\range{x_1}{x_k})$, that is, the first $k$  items of $H_t$, $\nfdh{}(H_t^k)$ the packing obtained by  from trying to pack $\squarehull{H_t^k{}}$ into $B'$, and $D(H_t^k)$ the empty area in $\nfdh{}(H_t^k)$.

Let $j+1$ be the smallest index in which  is not able to pack all items of $H_t^{j+1}$ into $B'$.
If $x_{j+1} \notin \nfdh{}(H_t^{j+1})$, then $\nfdh{}(H_t^{j+1}) = \nfdh{}(H_t^{j})$.
Otherwise, if $x_{j+1} \in \nfdh{}(H_t^{j+1})$, we know that the occupied area of $\nfdh{}(H_t^{j+1})$
less than the area of $\squarehull{x_{j+1}}$
must be less than the area of $\nfdh{}(H_t^{j})$.
Thus in both cases we have that

\begin{align*}
\area{\nfdh{}(H_t^{j})} &> \area{\nfdh{}(H_t^{j+1})} - \area{\squarehull{x_{j+1}}} \\
&= \area{B'} - D(H_t^{j+1}) - \area{\squarehull{x_{j+1}}} \\
&\geq \area{B'} - \eps^\reveps w \cdot 2 [(1 + \eps) w + 4\eps h]/2 - \area{\squarehull{x_{j+1}}} & (\cref{thm:nfdh-empty-volume}) \\
&\geq (1 + \eps) w \cdot 4 \eps h - \eps^\reveps w \cdot [(1 + \eps) w + 4\eps h] - (\eps^\reveps w)^2 \\
&\geq 4 \eps (1 + \eps) wh - \eps^\reveps w \cdot (1 + 5\eps) h - \eps^{2\reveps} wh & (w \leq h) \\
&= \brackets*{ 4(1 + \eps) - \eps^{\reveps - 1}(1 + 5\eps) - \eps^{2\reveps - 1} } \eps wh \\
&\geq \brackets*{ 4(1 + \eps) - \frac{1}{4^3}(1 + 5\eps) - \frac{1}{4^7} } \eps wh & (\eps \leq 1/4) \\
&= \brackets*{ \paren*{4 - \frac{1}{4^3} - \frac{1}{4^7}} + \paren*{4 - \frac{5}{4^3}}\eps } \eps wh \\
&\geq \frac{8}{\pi} \eps wh \\
&\geq \area{\squarehull{{H_t^*}}}.
\end{align*}

That is, $\nfdh{}(H_t^{j})$ fills an area at least as big as $\squarehull{{H_t^*}}$, and due to the ordering in $H_t$ such area is filled with the items of highest relative value. Thus, $\profits{\nfdh{}(H_t^{j})} \geq \profits{{H_t^*}}$.

Lastly, we move all circles that are entirely contained in the rightmost strip of length $2\eps w$ to a new bin of size $w \times 4\eps h$,
which leaves the rightmost area of $\eps w \times 4 \eps h$ empty since all circles have diameter at most $\eps^\reveps w$.
Then, by stacking this new bin on top of $B'$ we obtain a packing of the circles in a bin of size $w \times 8\eps h$, as shows <ref>.

pics/item/.style n args=3
code =

[fill=#2] (0,0) rectangle (#1, #1);
[fill=#3] (#1/2, #1/2) circle (#1/2);
(-left)  at ( 0,0) ;
(-right) at (#1,0) ;

pics/listitem/.style n args=3
code =

(c1) at (0,0)  item=[1]#2#3 ;
> 1
ıin 2, ...,
ȷint(ı- 1)
(cı) at ($(c\j-right)$)  item=#2#3 ;

(-end) at (c-right) ;

code =

[fill=customblue] (0,0) rectangle (8.4,5);

(-level1) at (0,0)    listitem=2, 2, 1.8, 1.8customorange1customorange2 ;
(-level2) at (0,2)    listitem=1.5, 1.4, 1.3, 1.3, 1.2, 1.2customorange1customorange2 ;
(-level3) at (0,3.5)  listitem=1.2, 1.1, 1, 0.9, 0.8, 0.8, 0.7, 0.7, 0.65customorange1customorange2 ;

(-tl) at (0,5) ;
(-tr) at (8.4,5) ;
(-bl) at (0,0) ;
(-br) at (8.4,0) ;

(bin1) at (0,0) packingw;

(augmentation-bl) at (8.4, 0) ;
[fill=customred] (augmentation-bl) rectangle ++ (1,5);

[local bounding box=pinkitems1] at (bin1-level1-end)  listitem=1.6custompink1custompink2 ;
(pinkitems2) at (bin1-level2-end)  listitem=1.2custompink1custompink2 ;
(pinkitems3) at (bin1-level3-end)  listitem=0.6, 0.6custompink1custompink2 ;

[red, dashed, line width=1mm] (, 0) – (, 5.65);

[Stealth-Stealth] ($ (bin1-bl) + (-0.5, 0) $) – node[left]  $4\varepsilon h$ ($ (bin1-tl) + (-0.5, 0) $);
[Stealth-Stealth] ($ (bin1-bl) + (0, -0.5) $) – node[below] $w$ ($ (bin1-br) + (0, -0.5) $);
[Stealth-Stealth] ($ (augmentation-bl) + (0, -0.5) $) – node[below] $\varepsilon w$ ++ (1, 0);
[Stealth-Stealth] (, 5.5) – node[above] $2 \varepsilon w$ ++ (2, 0);

(bin2) at ($ (bin1-br) + (2,0) $) packingw;

[fill=customred] (bin2-tl) rectangle ++ (8.4, 5);

(bin3-shift) at (3, 5);
at ($ (bin1-level1-end) + (bin3-shift) $)  listitem=1.6custompink1custompink2 ;
at ($ (bin1-level2-end) + (bin3-shift) $)  listitem=1.2custompink1custompink2 ;
at ($ (bin1-level3-end) + (bin3-shift) $)  listitem=0.6, 0.6custompink1custompink2 ;

[Stealth-Stealth] ($ (bin2-bl) + (0, -0.5) $)   – node[below] $w$ ($ (bin2-br) + (0, -0.5) $);
[Stealth-Stealth] ($ (bin2-br) + ( 0.5, 0) $) – node[right]  $8\varepsilon h$ ($ (bin2-tr) + (0.5, 5) $);

Transforming the packing of medium items in a bin of size $(1 + \eps) w \times 4\eps h$ obtained by  into a packing in a bin of size $w \times (1 + 8\eps h)$.

§.§ Structured Packing of the  Items

From <ref>, we know that there is a super-optimal structured packing for the instance $(\cali, w, h, p)$, if we allow some increase in the size of the knapsack.
Thus, we define ${\Hat{h} = (1 + 192\eps)h}$ to acknowledge the increase in the height of the knapsack and given a gap-structured partition $H_t, S_0, S_1, \dots$ of $\cali$,
we design an algorithm to find a super-optimal structured packing only of $\struct{\cali}{t}$.
Hence, in this subsection we deal with the instance $(\struct{\cali}{t}, w, \Hat{h}, p)$.

Now we need some more notation.
For $j \geq 0$, let $\Hat{\calt}_j = \srange{t_1}{t_{\Hat{T}_j}}$ be the set of different radii among circles of $S_j$, where $\Hat{T}_j = |\Hat{\calt}_j|$. Each set $\Hat{\calt}_j$ is associated with a tuple $(\range{\Hat{n}_j^1}{\Hat{n}_j^{\Hat{T}_j}})$ of demands, where $\Hat{n}_j^k$ is the number of circles of radius $t_j^k$ contained in $S_j$, for $k=1,\ldots,\Hat{T}_j$.
A configuration of $S_j$ is a tuple $C = (c_1,\ldots,c_{\Hat{T}_j})$ where each $c_k$ is the number of circles of radius $t_j^k$ in $C$, for $k=1,\ldots,\Hat{T}_j$. We define $|C| = \sum_{k=1}^{\Hat{T}_j} c_k$ and we say $C$ has $|C|$ circles. The area of a configuration $C$, denoted by $\area{C}$, is the sum of the area of every circle in $C$.
We say a configuration $C$ of $S_j$ is feasible if its circles fit in a bin of level $j$.
We denote the set of all feasible configurations of $S_j$ by $\Hat{\calc}_j$.
The next lemma states bounds on the number of circles that fit in a bin and the number of feasible configurations.

For any level $j \geq 0$ and configuration $C \in \Hat{\calc}_j$, if $h/w \in \bigO(1)$ then $|C|$ is bounded by a constant $\constantsizeconfig{j}$ and $|\Hat{\calc}_j|$ is bounded by a polynomial in $n$.

Since the circles of $S_j$ have a minimum radius $\rmin{j} \geq \eps^{\reveps^2 - \reveps + 1} w_j / 2$, the maximum number of circles that fit in a bin of level $j$ is bounded by

\begin{equation*}
\frac{w_j h_j}{\area{\rmin{j}}}
= \frac{w_j h_j}{\pi(\rmin{j})^2}
\leq \frac{w_j h_j}{\pi (\eps^{\reveps^2 - \reveps + 1} w_j/2)^2}
= \frac{4}{\pi} r^{2\reveps^2 - 2\reveps + 2} \frac{h_j}{w_j}
:= \constantsizeconfig{j},
\end{equation*}

which is constant under the assumption that $h/w \in \bigO(1)$. Then, the maximum number of feasible configurations of $S_j$ is at most $\binom{n}{\constantsizeconfig{j}} \in \bigO(n^{\constantsizeconfig{j}})$, thus polynomial in $n$.

Hereafter, we refer to a feasible configuration simply as a configuration. We want to determine a subset of configurations (of all levels) that together lead to an optimal structured packing of $\struct{\cali}{t}$.
For a configuration $C \in \Hat{\calc}_{j}$, let $\Hat{f}_{j}(C)$ be the number of empty subbins of size $w_{j+1} \times \Hat{h}_{j+1}$ available for circles of level $j+1$ onward.
Consider the following decision variables:

* [items][l]$x_j^C$:  the number of times configuration $C \in \Hat{C}_j$ is used in level $j$;

* [items][l]$b_j$:  the number of empty bins of size $w_j \times \Hat{h}_j$ available for circles of level $j$;

* [items][l]$z_i$:  binary variable that indicates if circle $s_i \in \struct{\cali}{t}$ is packed or not.

We present an integer program, named $\Fexact$, to find an optimal structured packing of $\struct{\cali}{t}$ into a knapsack of size $w \times \Hat{h}$.

()       $\max \quad \displaystyle \sum_{s_i \in \struct{\cali}{t}} z_i \profit{i}$

∑_C ∈_j x_j^C c_k    ≤n_j^k                 ∀  j ≥0, k ∈[T_j],

[r]∑_s_i ∈S_j : r_i = t_j^k z_i    = ∑_C ∈_j x_j^C c_k                         ∀  j ≥0, k ∈[T_j],

∑_C ∈_j x_j^C    = b_j                             ∀  j ≥0,

[r]∑_C ∈_j-1 f_j-1(C) x_j-1^C    ≥b_j                                  ∀  j ≥1,

b_0    = 1,

z_i    ∈               ∀  s_i ∈t,

b_j    ∈_+                                                        ∀  j ≥0,

x_j^C    ∈_+                                                      ∀  j ≥0, C ∈_j.

Constraints (<ref>) assure that the demand of each size is not surpassed.
Constraints (<ref>) determine which circles are packed, based on the chosen configurations.
Note that the objective function enforces that among circles of the same radius, the ones of highest profit are selected.
Constraints (<ref>) define the number of bins used in each level, while constraints (<ref>) limit the number of empty bins available for the subsequent levels, based on the chosen configurations.
Finally, constraint (<ref>) guarantees that only one knapsack is used and
constraints (<ref>)-(<ref>) define the scope of the variables.

Note that the number of variables and constraints of $\Fexact$ is bounded by a polynomial in $n$, therefore it is possible to solve its linear relaxation in polynomial time.
However, a fractional solution of $\Fexact$ may have too many fractional variables, which could prevent our rounding strategy to yield a solution that causes only a small increase in the knapsack.
For this reason, we modify the instance and consider a similar integer program, as described next.

We modify the original instance by rounding the radii of the circles so that we have a constant number of different radii in each level.
For this purpose, let $R_j = \set{ \rmin{j}(1 + \eps)^k : k \geq 0, \rmin{j}(1 + \eps)^k < \rmax{j} } \cup \set{\rmax{j}} $.
For each level $j$ we round up the radius of the circles of $S_j$ to the closest value in $R_j$.
We denote the rounded radius of a circle $s_i$ by $\Bar{r}_i$, and we refer to such circles as scaled circles.
We define $\calt_j = \srange{t_j^1}{t_j^{T_j}}$ and $(\range{n_j^1}{n_j^{T_j}})$ for the scaled circles analogously as previously.
The following lemma shows that the number of different radii in each level is now constant.

For any level $j$, the number $T_j$ of different rounded radii is at most $\reveps^3 \ln(\reveps)$.

Using the fact that for any number $x > -1$ it holds that

\begin{equation*}
\frac{x}{1+x} \leq \ln(1 + x) \leq x,
\end{equation*}

we have that

\begin{equation*}
\log_{1 + \eps} \reveps
= \frac{\ln(\reveps)}{\ln(1 + \eps)}
\leq \paren*{1 + \frac{1}{\eps}} \ln(\reveps),
\end{equation*}

which implies that

\begin{equation}\label{eq:bound-different-radii_log<=ln}
\log_{1+\eps} \reveps \leq (\reveps+1)\ln(\reveps).
\end{equation}

Recall that the radii of the circles of $S_j$ are rounded up to values of the set $ R_j = \set{ \rmin{j}(1 + \eps)^k : k \geq 0, \rmin{j}(1 + \eps)^k < \rmax{j} } \cup \set{\rmax{j}} $.
Since $T_j$ is bounded by $\size{R_j}$ and $k \leq \ceil{\log_{1 + \eps} (\rmax{j} / \rmin{j})}$, we have that

\begin{align*}
T_j &\leq \log_{1 + \eps} \paren*{ \frac{\rmax{j}}{\rmin{j}} } + 2 \\
&= \log_{1 + \eps} (\reveps^{\reveps(\reveps-1)}) + 2 \\
&= \reveps (\reveps-1) \log_{1 + \eps} (\reveps) + 2 \\
&\leq \reveps (\reveps-1) (\reveps+1) \ln(r) + 2  \qquad \text{(from inequality~\eqref{eq:bound-different-radii_log<=ln})} \\
&= \reveps^3 \ln(r) - \reveps^2 \ln(r) + 2 \\
&\leq \reveps^3 \ln(r)
\end{align*}

for $\eps \leq 1/4$.

Since the number of different radii is now constant, we have a better bound on the number of configurations in each level.

For any level $j$, the number of different configurations of scaled circles of $S_j$ is bounded by a constant.

The bound $\constantsizeconfig{j}$ defined in <ref> to the maximum number of circles that fit in one bin of level $j$ still holds after rounding their radii.
Then, since a configuration is composed of $T_j$ values, and each value can range from $0$ to $\constantsizeconfig{j}$, the total number of possible configurations is at most

\begin{equation*}
(\constantsizeconfig{j}+1)^{T_j} \leq \paren*{ \frac{4}{\pi} \reveps^{2\reveps^2-2\reveps+2} \frac{h_j}{w_j} + 1}^{ r^3\ln(r)},
\end{equation*}

which is constant under the assumption that $h/w \in \bigO(1)$.

With these new bounds and <ref>, we can check the feasibility of a configuration and find its corresponding packing in constant time.

For any level $j$, given a configuration $C$ of scaled circles of $S_j$, we can decide if $C$ is feasible, and in the affirmative case, for any constant $\gamma > 0$, we obtain a packing of $C$ in a bin of size $w_j \times (1+\gamma)h_j$, in constant time.

Let $\cals_C$ be the set of circles of $C$.
Since the number of different radii is constant from <ref> and the circles of $\cals_C$ have a constant minimum radius $r_{\min}^j$,
we can use the algorithm from <ref> with $\gamma$ to obtain a solution for the  instance $(\cals_C,w_j,h_j)$.
If the number of bins used in this solution is greater than $1$, we say that the configuration $C$ is unfeasible.
Otherwise, the solution consists of a packing of the circles of $C$ into exactly one bin of size $w_j \times (1+\gamma)h_j$.
The algorithm from <ref> runs in polynomial time on the number of circles. Since the number of circles of a configuration of scaled circles is bounded by a constant from <ref>, the algorithm takes constant time.

Hence, for each level $j$ we use <ref> to determine the sets $\calc_j$ of all feasible configurations of scaled circles of $S_j$.
To compensate the possible increase in the radius of the circles after the scaling, we use augmented bins of size $w'_j \times h'_j$, where $w'_j = (1+\eps)w_j$ and $h'_j=(1+\eps)(1+16\eps)\Hat{h}_j$.
We now use another IP, similar to $\Fexact$, to find an optimal structured packing of $\struct{\cali}{t}$ after the scaling.
In this new IP, instead of computing $\Hat{f}_j(C)$, we estimate its value based on <ref>, by defining

\begin{equation*}
f_{j}(C) =  \frac{w'_{j-1} h'_{j-1} - (1+16\eps)\area{C}}{w'_j h'_j},
\end{equation*}

which is a lower bound on the number of empty subbins of size $w'_{j+1} \times h'_{j+1}$ after packing a configuration $C \in \calc_j$ in a bin of size $w'_j \times h'_j$.
We describe next the IP $\Frounded$, which finds an optimal structured packing of the scaled circles.
The decision variables $x$, $z$ and $b$ have the same meaning as in $\Fexact$.

()       $\max \quad \displaystyle \smashoperator[lr]{ \sum_{s_i \in \struct{\cali}{t}} } z_i \profit{i}$

∑_C ∈_j x_j^C c_k    ≤n_j^k                 ∀  j ≥0, k ∈[T_j],

[r]∑_s_i ∈S_j : r_i = t_j^k z_i    = ∑_C ∈_j x_j^C c_k                         ∀  j ≥0, k ∈[T_j],

∑_C ∈_j x_j^C    = b_j                             ∀  j ≥0,

[r]∑_C ∈_j-1 f_j-1(C) x_j-1^C    ≥b_j                    ∀  j ≥1,

b_0    = 1,

z_i    ∈               ∀  s_i ∈t,

b_j    ∈_+                                                               ∀  j ≥0,

x_j^C    ∈_+                                                             ∀  C ∈_j.

Despite the increase of the circles and the error caused by the function $f_j(C)$, $\Frounded$ still gives a good solution if we increase the size of the knapsack by a small factor.
The next lemma states that if we use a knapsack of size $w' \times h'$, the optimum value of $\Frounded$ is at least the optimum value given by $\Fexact$.

For an instance $(\struct{\cali}{t}, w, \Hat{h}, p)$, $\opt(\Frounded) \geq \opt(\Fexact)$ if $\Frounded$ considers an augmented knapsack of size $w' \times h'$.

Given a level $j$, for each configuration $C \in \calc_j$ of the scaled circles of $S_j$, let $\calr_j^C$ be the set of configurations of the original circles of $S_j$ that, after scaling the circles, became equivalent to $C$.
Let $(\Hat{x}, \Hat{b}, \Hat{z})$ be an optimal solution of $\Fexact$ for $(\struct{\cali}{t}, w, \Hat{h}, p)$.
We build a solution $(x, b, z)$ of $\Frounded$ as follows: $b = \Hat{b}$, $z = \Hat{z}$, and $x_j^C = \sum_{D \in \calr_j^C} \Hat{x}_j^D$ for each $j\geq 0$ and $C \in \calc_j$.

By construction both solutions have the same objective value. It remains to prove the feasibility of $(x,b,z)$.
Observe that by the definition of $x_j^C$ we have that

\begin{equation*}
\sum_{C \in \calc_j} x_j^C = \sum_{C \in \calc_j} \sum_{D \in \calr_j^C} \Hat{x}_j^D = \sum_{\Hat{C} \in \Hat{\calc}_j} \Hat{x}_j^{\Hat{C}}.
\end{equation*}

Thus, constraints (<ref>)–(<ref>) are satisfied by $(x,b,z)$.
It only remains to show the satisfiability of constraints (<ref>).
For that, fixing a level $j$, consider a configuration $\Hat{C} \in \Hat{\calc}_j$ of original circles and its counterpart $C \in \calc_j$ of scaled circles.
We show that $f_{j}(C) \geq \Hat{f}_{j}(\Hat{C})$.

\begin{align}
f_{j}(C) &= \frac{w'_{j-1} h'_{j-1} - (1+16\eps)\area{C}}{w'_j h'_j} \nonumber \\
&\geq \frac{w'_{j-1} h'_{j-1} - (1+16\eps) (1+\eps)^2\area{\Hat{C}}}{w'_j h'_j} \nonumber \\
&= \frac{(1+16\eps)(1+\eps)^2 w_{j-1} h_{j-1} - (1+16\eps) (1+\eps)^2\area{\Hat{C}}}{(1+16\eps)(1+\eps)^2 w_j h_j} \nonumber \\
&= \frac{w_{j-1} h_{j-1} - \area{\Hat{C}}}{ w_j h_j} \label{eq:free-area-opt} \\
&\geq \Hat{f}_{j}(\Hat{C}), \nonumber
\end{align}

since <ref> is an area-based upper bound on the number of subbins that fit in the empty space.
With this result we obtain that for any level $j \geq 1$,

\begin{align*}
b_j &= \Hat{b}_j \\
&\leq \sum_{ \Hat{C} \in \Hat{\calc}_{j-1} } \Hat{f}_{j-1}(\Hat{C}) \Hat{x}_{j-1}^{\Hat{C}} \\
&= \sum_{C \in \calc_{j-1}} \sum_{ D \in \calr_{j-1}^C } \Hat{f}_{j-1}(D) \Hat{x}_{j-1}^D \\
&\leq \sum_{C \in \calc_{j-1}} f_{j-1}(C) x_{j-1}^C.
\end{align*}

Thus $(x,b,z)$ is a feasible solution for $\Frounded$ with same objective value as the solution $(\Hat{x}, \Hat{b}, \Hat{z})$ for $\Fexact$.
Consequently, $\opt(\Frounded) \geq \opt(\Fexact)$.

We intend to use $\Frounded$ to obtain an optimal fractional solution $(x^*, b^*, z^*)$ and then round up the fractional variables $x^*$, obtaining a set of configurations that we use to build a feasible solution in an augmented knapsack.
However, an arbitrary optimal fractional solution of $\Frounded$ may not be sufficient for this purpose, since there is no guarantee that the extra area that comes from rounding up the fractional solution is small enough to fit in the augmented height.
To have this guarantee, we need to assure to properties from the fractional solution:
There cannot be more than one fractional $x$ variable from level $0$, since any of such variables when rounded up would correspond to another knapsack, whose area is prohibitive;
and the number of fractional $x$ variables in levels from $1$ onward must be small enough to be able to pack the extra bins originated from the rounding up in a strip of small height, i.e., $\bigO(\eps) h$.

We address such properties as follows.
The appearance of fractional $x$ variables from level $0$ can be entirely avoided by simply not relaxing their integrality in the linear relaxation of $\Frounded$.
Let $\milpFrounded$ be such MILP obtained by relaxing the integrality of all variables of $\Frounded$ except the ones of $x_0$.
Since the number of configurations in each level is constant from <ref>, $\milpFrounded$ has a constant number of integer variables, and by the result of <cit.>, it is known that such MILP can be solved in polynomial time.
Now regarding the $x$ variables from level $1$ onward, we particularly desire that the number of non-null $x$ variables in each level is bounded by a small constant.
We say that such a solution is balanced.
To obtain a balanced fractional solution, we define another integer program:
$\Flevel[j][A, B]$ finds an optimal solution for level $j$ using exactly $A$ bins of its level, and leaving exactly $B$ empty subbins available to level ${j+1}$. Again, the variables $x$ and $z$ have the same meaning as in $\Fexact$.

[][j][A, B]       $\max \quad \displaystyle \sum_{s_i \in S_j} z_i \profit{i}$

∑_C ∈_j x_j^C c_k    ≤n_j^k               ∀  k ∈[T_j],

[r]∑_s_i ∈S_j : r̅_i = t_j^k z_i    = ∑_C ∈_j x_j^C c_k                 ∀  k ∈[T_j],

∑_C ∈_j x_j^C    = A,

[r]∑_C ∈_j f_j(C) x_j^C    = B,

x_j^C    ∈_+                                                           ∀  C ∈_j,

z_i    ∈               ∀  s_i ∈S_j.

Given a feasible solution $(x,b,z)$ to $\milpFrounded$, we use $\Flevel[j][A, B]$ at each level $j \geq 1$, with parameters $A$ and $B$ derived from $x$ and $b$, as shown in <ref>.
This way we can take advantage of the fact that despite the number of levels being at most $n$, the number of constraints in each level is constant.
<ref> comes from the fact that $\Flevel$ has a constant number of constraints.

Instance $(\struct{\cali}{t}, w, \Hat{h}, p)$.

Balanced solution $(\Tilde{x}, b, \Tilde{z})$ to $\milpFrounded$.
$(x, b, z) \gets \text{optimal solution of } \milpFrounded$
each $j \geq 1$
$A \gets \sum_{C \in \calc_j} x_j^C$
$B \gets b_{j+1}$
$(\Tilde{x}_j, \Tilde{z}_j) \gets \text{linear relaxation of } \Flevel[j][A, B]$

$\Tilde{x} \gets (x_0, \Tilde{x}_1, \Tilde{x}_2, \ldots)$
$\Tilde{z} \gets (z_0, \Tilde{z}_1, \Tilde{z}_2, \ldots)$
$(\Tilde{x}, b, \Tilde{z})$

<ref> returns an optimal balanced solution of $\milpFrounded$ for instance $(\struct{\cali}{t}, w, \Hat{h}, p)$.

Let $(x^*, b^*, z^*)$ be an optimal fractional solution of $\milpFrounded$ and let $(\Tilde{x}, b^*, \Tilde{z})$ be the solution obtained by <ref> for $(\struct{\cali}{t}, w, \Hat{h}, p)$.
First note that the solution $(x_j^*, z_j^*)$ given by the restriction of $x^*$ and $z^*$ to the circles of $S_j$ is a feasible solution to the linear relaxation of $\Flevel[j][\sum_{C \in \calc_j} (x_j^C)^*, b_{j+1}^*]$ as in line <ref> of the algorithm. Thus the objective value of the obtained solution $(\Tilde{x}, b^*, \Tilde{z})$ is at least the value of the optimal one $(x^*, b^*, z^*)$. On the other hand, the value of $(\Tilde{x}, b^*, \Tilde{z})$ cannot be greater than the value of $(x^*, b^*, z^*)$. Otherwise, if for some $j \geq 1$ the value of $(\Tilde{x}_j, \Tilde{z}_j)$ is greater than the value of $(x_j^*, z_j^*)$, then we can simply replace the latter by the former and obtain a feasible solution to $\milpFrounded$ whose profit is greater than the one given by $(x^*, b^*, z^*)$, contradicting its optimality.
Therefore, $(\Tilde{x}, b^*, \Tilde{z})$ is an optimal solution to $\milpFrounded$, and since $\Flevel[j]$ has $2T_j + 2$ constraints, $\Tilde{x}_j$ has at most $2T_j + 2$ non-null variables.

Hereafter, given an $n$-dimensional vector $x = (x_1,\ldots,x_n)$, we define the ceil of $x$ as $\ceil{x} = (\ceil{x_1},\ldots,\ceil{x_n})$.
Let $(x^*, b^*, z^*)$ be an optimal balanced fractional solution of $\milpFrounded$ given by the  procedure.
We round the variables $x^*$ up to the next integer, yielding a collection of configurations represented by the vector $\ceil{x^*}$.
The total extra area necessary to contemplate the extra bins created by the rounding is small.

Let $(x^*, b^*, z^*)$ be an optimal balanced fractional solution of $\milpFrounded$.
The extra bins created after rounding the variables $x^*$ to $\ceil{x^*}$ fit into a strip of size $w' \times \eps h'$.

Since $(x^*, b^*, z^*)$ is balanced, from <ref> we have that for each level $j \geq 1$, at most $2T_j + 2$ variables $x_j$ were rounded.
Recall from <ref> that $T_j \leq \reveps^3 \ln(\reveps)$.

\begin{equation*}
2T_j + 2 \leq 2\reveps^3\ln(\reveps) + 2.
\end{equation*}

Let $D$ be a rectangle of size $w' \times \eps h'$. Since we assume $w \leq h$, we have $\area{D} \geq \eps w'^2$.
Recall that $w'_j = h'_j = \eps^{\reveps(t+(j-1)\reveps)+\reveps-1} w'$, and moreover, that $r \geq 4$ and $t \geq 1$.
First we analyze level $1$ separately.
By definition, we have $w'_1 = \eps^{\reveps t + \reveps - 1} w' \leq \eps^{2\reveps - 1} w'$, because $t \geq 1$.
Then the number of bins of size $w'_1 \times h'_1$ that fit into $D$ is bounded by

\begin{equation*}
\frac{\area{D}}{{w'}_1^2} \geq \eps \frac{{w'}^2}{{w'}_1^2} \geq \reveps^{4\reveps - 3} \geq 2T_1 + 3.
\end{equation*}

This means that $D$ is sufficiently large to accommodate all extra bins of level $1$, and it still has space for at least one more bin of size $w'_1 \times h'_1$.
Similarly, we show that for $j \geq 2$, one bin of size $w'_{j-1} \times h'_{j-1}$ is sufficient to accommodate the extra bins of level $j$ and it still has space for at least one more bin of size $w'_j \times h'_j$.
Note that $w'_j = \eps^{r^2} w'_{j-1}$. Then the result follows from direct calculation.

\begin{equation*}
\frac{{w'}_{j-1}^2}{{w'}_j^2} = r^{2r^2} \geq 2 T_j + 3.
\end{equation*}

Since after packing the extra bins of level $1$ in $D$ it still has space for at least one free bin of level $1$, and for level $j \geq 2$, one bin of level ${j-1}$ is sufficient to pack all the extra bins plus one of level $j$, we conclude that all the extra bins of every level fit into $D$.

Observe that a solution of the linear program $\Frounded$ gives a set of configurations used in each level, where each configuration represents a bin.
To build a packing, for each configuration, we obtain a packing in a bin of its respective level.
Then we distribute these packings (bins) into the knapsack.

Given an instance $(\struct{\cali}{t}, w, \Hat{h}, p)$,
for each level $j$ let $X_j$ be a collection (allowing duplication) of configurations of the scaled circles of $S_j$, considering bins of size $w'_j \times h'_j$.
Given a constant $\gamma > 0$, there is an algorithm that finds a packing of maximum profit of the original circles that correspond to the configurations of $X_j$ in bins of size $w'_j \times (1 + \gamma) h'_j$, in polynomial time.

For each configuration $C \in X_j$,  we use <ref> to obtain a packing of the scaled circles of $C$ in a bin of size $w'_j \times (1+\gamma)h'_j$, in constant time.
Now it remains to replace the scaled circles with original ones in such a way that the total profit is maximum. For that, it is enough to choose the original circles of highest profit, as follows.
For each $k = 1,\ldots,T_j$, let $\eta_k$ be the total number of scaled circles of radius $t_j^k$ within the collection $X_j$.
We sort $S_j$ in non-increasing order of profit, and we substitute the $\eta_k$ circles of radius $t_j^k$ with the $\eta_k$ original circles of highest profit, among the ones whose rounded up radius is $t_j^k$.
In the case that $\eta_k > n_j^k$, which may happen when $X_j$ comes from a rounded up fractional solution of $\Frounded$, we simply pack all $n_j^k$ original circles whose rounded up radius is $t_j^k$, since it trivially maximizes the profit originating from the circles of such radius.
This procedure can be done in $\bigO(n\log n)$ time, thus polynomial.

Instance $\calz = (\struct{\cali}{t}, w, \Hat{h}, p)$; and constant $\eps$.
A super-optimal solution to $\calz$ in a knapsack of size $(1 + \bigO(\eps)) w \times (1 + \bigO(\eps)) h$.

each level $j \geq 0$
Let $R_j = \set{ r_{\min}^j(1 + \eps)^k : k \geq 0, r_{\min}^j(1 + \eps)^k < r_{\max}^j } \cup \set{r_{\max}^j} $.
Scale the circles of $S_j$ by rounding up their radii to values of $R_j$.
Obtain the set of feasible configurations $\calc_j$ of the scaled circles of $S_j$.

$(x^*, b^*, z^*) \gets \algBalanced{}(\calz)$.
Build a packing $P$ from the configurations of $\ceil{x^*}$ into a knapsack of size $w \times (1+\bigO(\eps))h$.
packing $P$.

Finally, we give an algorithm that, for an instance $(\cali,w,h,p)$ of  where $h/w \in \bigO(1)$,
and a positive constant $\eps \leq 1/4$, it produces an almost optimal solution under resource augmentation. See <ref>.

Given an instance $(\struct{\cali}{t}, w, \Hat{h}, p)$ of  with $h/w \in \bigO(1)$ and a constant $\eps \leq 1/4$, <ref> obtains a packing of a subset $I \subseteq \struct{\cali}{t}$ of circles in a knapsack of size $(1 + \eps)w \times (1+1911\eps)h$ such that
$\profits{I} \geq \optKP{\struct{\cali}{t}}{w}{h}$, in polynomial time in the size of the instance.

Let $(x^*, b^*, z^*)$ be the optimal balanced fractional solution obtained in <ref>.
From <ref>, we know that the configurations corresponding to $\ceil{x^*}$ fit into a knapsack of size $w' \times (1+\eps)h'$.
We then use <ref> with $\gamma = \eps$ to find a packing $P'$ of circles corresponding to the configurations given by $\ceil{x^*}$ into bins of size $w'_j \times (1 + \eps)^2 h'_j$ for each level $j$.
Thus $P'$ fits in a knapsack of size $(1 + \eps) w \times (1 + \eps)^2 h'$.
Since $(1 + \eps)^2 h' = (1 + \eps)^3 (1 + 16\eps) (1 + 192\eps) h \leq (1 + 1911\eps) h$ for $\eps \leq 1/4$, we have that $P^*$ fits into a knapsack of size $(1 + \eps) w \times (1 + 1911\eps) h$.

§.§ Complete Algorithm for  and

At last, we combine all the procedures of the previous subsections to obtain the complete algorithm for the , described in <ref>.
The algorithm derives a gap-structured partition of the instance (<ref>), and by guessing a set of medium items, it finds a super-optimal packing of the medium items (<ref>) and of the  items (<ref>).

Instance $(\cali, p, w, h)$ of ; and constant $\eps$.
A super-optimal packing in a knapsack of size $(1 + \bigO(\eps)) w \times (1 + \bigO(\eps)) h$.
Let $\reveps = 1/\eps$.
Define $G_i = \set{ s_j \in \cali : \eps^{\reveps i}w \geq d_j > \eps^{\reveps(i+1)}w }$, for $i \geq 0$.
Define $H_\ell = \set{ G_i : i \equiv \ell \pmod{\reveps} }$, for $0 \leq \ell < \reveps$.
each $t$ from $1$ to $\reveps-1$
Define $S_j = \bigcup_{i = t+(j-1)\reveps+1}^{t+j\reveps-1} G_i$, for every integer $j \geq 0$.
Define $w_0 = w$, $h_0 = h$, and $w_j = h_j = \eps^{\reveps (t+(j-1)\reveps) + \reveps - 1}w$, for $j \geq 1$.
$P_H \gets \algPackingMedium{}((H_t, w, h, p), \eps)$.
$P_\cals \gets \algStructuredPacking{}((\struct{\cali}{t}, w, \Hat{h}, p), \eps)$.
$P_t \gets$ $P_H$ stacked on top of $P_\cals$.

packing $P_t$ of maximum profit.

Given an instance $(\cali, w, h, p)$ of  with $h/w \in \bigO(1)$ and a constant $\eps \leq 1/4$, <ref> obtains a packing of a subset $I \subseteq \cali$ of circles in a knapsack of size $(1 + \eps)w \times (1+1919\eps)h$ such that
$\profits{I} \geq \optKP{\cali}{w}{h}$, in polynomial time in the size of the instance.

Let $I^* \subseteq \cali$ be the set of circles of an optimal solution.
Note that in some iteration of <ref> the set $H_t$ will be such that $\area{H_t \cap I^*} \leq 2 \eps wh$.
Thus, in such iteration $t$, line $5$ obtains a super-optimal packing of the medium items in a knapsack of size $w \times 8\eps h$ from <ref>,
and line $6$ obtains a super-optimal packing of the  items in a knapsack of size $w \times (1 + 1911\eps) h$ from <ref>.
Thus, $P_t$ consists of a super-optimal packing in a knapsack of size $(1 + \eps) w \times (1 + 1919\eps) h$.

We show next that with only a few modifications, <ref> works for the  as well.

Let $(\cali, w, h, p, m)$ be an instance of . If $h/w \in \bigO(1)$, then for any constant $\eps > 0$ we can obtain, in polynomial time, a packing of $I \subseteq \cali$ in at most $m$ knapsacks of size $(1 + \eps) w \times (1 + 1920\eps)h$ such that $\profits{I} \geq \optMKP{\cali}{m}{w}{h}$.

We show what modifications are necessary in each of the three main steps of <ref>, namely the gap-structured partitioning, the packing of the medium items, and the packing of the  items.

Starting with the gap-structured partitioning, let $I^*$ be the circles of an optimal solution.
Since we now have $m$ knapsacks, we choose the set of medium items $H_t$ so that $\area{H_t \cap I^*} \leq 2 \eps \area{I^*} \leq 2 \eps mwh$ and $t \geq 1$.
The structural theorem presented in <ref> works the same, since given any feasible packing for the  instance, we can transform it into a structured packing where each knapsack has size $w \times (1 + 192\eps) h$ by simply applying <ref> for each knapsack individually.

Regarding the packing of the medium items, we can use <ref> considering a knapsack of size $w \times mh$, in which <ref> gives us a super-optimal packing of the medium items in a bin $B$ of size $w \times 8\eps mh$.
We only need to transform $B$ into $m$ bins of small height.
For that, since the packing obtained by <ref> follows a shelf-like manner from the  algorithm, we can simply partition $B$ in $m$ strips of height $8\eps h$, and increase the height of each strip to match the base of the closest shelf in order to remove the intersection with the packed items.
Since the size of the medium items is bounded by $\eps^\reveps w$ because $t \geq 1$, this procedure makes each of the bins have height at most $8 \eps h + \eps^\reveps w \leq 9 \eps h$.

At last, to obtain a super-optimal packing of the  items, it suffices to change constraint (<ref>) of $\Frounded$ to $b_0 \leq m$, and this modification does not affect the behavior of <ref>. Therefore, the result of <ref> remains the same for the  problem.

Thus, applying <ref> with the aforementioned modifications gives us a super-optimal packing for the $(\cali, w, h, p, m)$ instance in at most $m$ knapsacks of size $(1 + \eps) w \times (1 + 1920) h$.

Note that <ref> only runs in polynomial time under the assumption that $h/w \in \bigO(1)$.
However, with the result of <ref>, we can derive a polynomial-time algorithm for the  with unconstrained ratio between $w$ and $h$,
thus settling the result for the  with unconstrained $m$ and $h/w$.

Let $(\cali, w, h, p, m)$ be an instance of  and $\eps > 0$ be a constant. There is a polynomial-time algorithm that finds a packing of a subset $I \subseteq \cali$ in at most $m$ knapsacks of size $(1 + \eps) w \times (1 + 3844\eps) h$ such that $\profits{I} \geq \optMKP{\cali}{m}{w}{h}$.

First we show that we can transform any packing $P$ in a bin of size $w \times h$ into another packing $P'$ in a bin $B'$ of size of $w \times (1 + 4\eps) h$ so that $B'$ can be partitioned in strips of size $w \times w/\eps$ in such a way that no circles in $P'$ overlap the boundaries of the strips.
For that, we start by partitioning the original bin of size $w \times h$ in strips of size $w \times w/\eps$.
Since each circle has diameter at most $w$, a region of size $w \times 2w$ centered at each strip contains all circles that overlap the boundaries.
We can thus move all these circles to a bin of width $w$ and height $h/(w/\eps) \cdot 2w = 2\eps h$.

Now the original bin of size $w \times h$ has the desired property of no circle overlapping the boundary of the strips of size $w \times w/\eps$, but we are left with a bin of size $w \times 2\eps h$ where this may not be true.
We then apply the same procedure recursively in this bin, until the desired property holds true for all the bins created.
Stacking these bins on top of each other, we obtain a new bin $B'$ with the desired property and whose height is

\begin{equation*}
h' \leq h + \sum_{i=1}^{\infty} (2\eps)^i h = h + \frac{2\eps}{1 - 2\eps} h \leq (1 + 4\eps) h,
\end{equation*}

since $1/(1-2\eps) \leq 2$ for $\eps \leq 1/4$.

Given the instance $(\cali, w, h, p, m)$ of , we define $q = h'/(w/\eps) = (1 + 4\eps) \eps h/w$ and create the instance $\calz' = (\cali, w, w/\eps, p, qm)$ of . From the previous result, we know that $\optMKP{\cali}{qm}{w}{w/\eps} \geq \optMKP{\cali}{m}{w}{h}$.
Since $(w/\eps)/w = \reveps \in \bigO(1)$, we can use the algorithm of <ref> to obtain a super-optimal packing for instance $\calz'$ in at most $m$ bins of size $(1 +\eps) w \times (1 + 1920\eps) w/\eps$.
Stacking each group of $q$ bins of size $w \times w/\eps$ on top of each other, we obtain $m$ bins of width $(1 + \eps) w$ and height $q (1 + 1920\eps) w/\eps = (1 + 1920\eps) (1 + 4\eps) h \leq (1 + 3844\eps) h$ for $\eps \leq 1/4$.

§.§ Resource Augmentation in only One Dimension

The previous results use resource augmentation in both dimensions.
This is due to the scaling of the circles and subbins done in <ref>.
We are able to remove the necessity of resource augmentation in the width of the bin, leaving only the height augmented.
For that, we handle level $0$ in a particular manner.
The idea is to scale the circles of level $0$ by a more fine-grained factor, so that we can use the shifting algorithm of <ref> to obtain a packing of the scaled circles in a bin with height augmented by $\eps$.

To formally present the modifications, we first consider back the  problem under the assumption that $h/w \in \bigO(1)$.
Recall that $\constantsizeconfig{0} = \frac{4}{\pi} \reveps^{2\reveps^2 - 2\reveps + 2} \frac{h}{w}$ is the bound on the number of circles of level $0$ that fit in a bin, as calculated in <ref>.
Instead of scaling the circles of level $0$ by powers of $(1 + \eps)$, we define $\delta = \eps^2/(6{\constantsizeconfig{0}}^2)$ and scale the circles by powers of $(1 + \delta)$, namely the values from the set $R_0 = \set{ \rmin{0} (1 + \delta)^k : k \geq 0, \rmin{0} (1 + \delta)^k < \rmax{0} } \cup \set{\rmax{0}}$.
We first show that despite the fact than $\delta$ is much smaller that $\eps$, the number of different sizes remain constant.

The number $T_0$ of different sizes of scaled circles of level $0$ is bounded by a constant, under the assumption that $h/w \in \bigO(1)$.

First recall that $\rmax{0} \leq w/2$ and $\rmin{0} \geq \eps^{\reveps t} w/2$, and thus $\rmax{0} / \rmin{0} \leq r^{\reveps t} \leq r^{\reveps(\reveps - 1)}$ since $t \leq \reveps - 1$.
Since $T_0$ is bounded by the size of $R_0$, we have that

\begin{align*}
T_0 &\leq \log_{1+\delta}\paren*{\frac{\rmax{0}}{\rmin{0}}} + 2 \\
&\leq \log_{1+\delta}(\reveps^{\reveps(\reveps-1)}) + 2 \\
&\leq \reveps(\reveps-1) \paren*{1 + \frac{1}{\delta}} \ln{\reveps} + 2 \\
&\leq \paren*{1 + \frac{96}{\pi^2} r^{4\reveps^2 - 4\reveps + 6} \frac{h^2}{w^2}} \reveps (\reveps - 1) \ln{\reveps} + 2 \\
&\leq 12 \reveps^{4\reveps^2 - 4\reveps + 9} \frac{h^2}{w^2}
\end{align*}

for $\eps \leq 1/4$, which is constant under the assumption that $h/w \in \bigO(1)$.

Now we show that by scaling the circles to powers of $1 + \delta$, we can obtain a packing of the scaled circles in a bin of size $w \times (1 + \eps) h$.

For any packing $P$ of circles of level $0$ in a bin $B_{w \times h}$, there is another packing $P'$ of the scaled circles in a bin of size $w \times (1 + \eps) h$.

Let $p_i = (x_i, y_i)$ be the center position of the circle $i$ in $P$.
Since $P$ is a packing, we know that $r_i \leq x_i \leq w - r_i$ and $r_i \leq y_i \leq h - r_i$ for any circle $i$, and $\dist{p_i}{p_j} \geq r_i + r_j$ for any two circles $i$ and $j$.
Now consider the circles positioned as in $P$ but with the radius scaled up to the closest value of $R_0$.
The scaled radius $\Bar{r}_i$ of any circle $i$ can increase only by a factor of at most $1 + \delta$, that is, $\Bar{r}_i / r_i \leq (1 + \delta)$, which implies that $r_i \geq \Bar{r}_i / (1 + \delta)$.
Furthermore, since $r_i \leq w/2 \leq h/2$, we have that $\Bar{r}_i \leq (1 + \delta) h/2$.
Using these inequalities, we can show that the distance between two scaled circles in $P$ becomes

\begin{align*}
\dist{p_i}{p_j} &\geq r_i + r_j \\
&\geq \frac{1}{1+\delta} (\Bar{r}_i + \Bar{r}_j) \\
&= \Bar{r}_i + \Bar{r}_j - \frac{\delta}{1+\delta} (\Bar{r}_i + \Bar{r}_j) \\
&\geq \Bar{r}_i + \Bar{r}_j + \delta h,
\end{align*}

and using the same reasoning, we can show that $\Bar{r}_i - \delta h \leq x_i \leq w - \Bar{r}_i + \delta h$ and $\Bar{r}_i - \delta h \leq y_i \leq h - \Bar{r}_i + \delta h$ for any circle $i$.
Therefore, this attribution is a $\delta h$-packing of the scaled circles in $B_{w \times h}$.
Using the result of <ref>, this $\delta h$-packing can be converted into a packing in a bin of width $w$ and height $(1 + n \sqrt{6\delta}) h \leq (1 + \constantsizeconfig{0} \sqrt{6 \cdot \eps^2/(6{\constantsizeconfig{0}}^2)} = (1 + \eps) h$.

Given an instance $(\cali, w, h, p)$ of  with $h/w \in \bigO(1)$ and a constant $\eps$,
we can obtain in polynomial time a packing of a subset $I \subseteq \cali$ of circles in a knapsack of size $w \times (1+\bigO(\eps))h$ such that $\profits{I} \geq \optKP{\cali}{w}{h}$.

We use <ref> only changing the scaling of the circles of level $0$ as explained here.
Since $T_0$ is bounded by a constant, the number of configurations of level $0$, which is bounded by $(\constantsizeconfig{0}+1)^{T_0}$, also remains constant, and thus we are still able to solve $\milpFrounded$ in polynomial time.
Therefore, <ref> continues to take polynomial time with this change and it gives us a super-optimal packing in a bin of size $(1 + \eps) w \times h'$ where $h' = (1 + \bigO(\eps)) h$.
We use the result of <ref> to convert the packing of the circles of level $0$ in a bin $B_{(1 + \eps) w \times h}$ to another one in a bin $B'_{w \times (1 + \eps) h'}$.
When doing this conversion, we also move any subbins of the further levels to the empty space of this new packing in $B'$, as necessary.
Note that since $\area{B} = \area{B'}$ and the configuration $C$ of circles of level $0$ remains the same, the value of $f(C)$ considering the bin $B'$ cannot be lower than its value in $B$, and therefore there is always enough space in the new packing to place the subbins.
After changing the packing of the circles of level $0$, we have the guarantee that the rightmost strip of size $\eps w \times h'$ contains only subbins of level $1$ onward, and thus we can rearrange them in a strip of size $w \times \eps h'$.
Stacking this strip on top of $B'$, we obtain a packing of the circles in a bin of size $w \times (1 + \bigO(\eps)) h$.

In possession of this result, we can apply the same procedures done in <ref> to obtain an equivalent theorem for the more general case of the  with unconstrained ratio between $h$ and $w$.

Given an instance $(\cali, w, h, p, m)$ of  and a constant $\eps$,
we can obtain in polynomial time a packing of a subset $I \subseteq \cali$ of circles in at most $m$ knapsacks of size $w \times (1+\bigO(\eps))h$ such that $\profits{I} \geq \optMKP{\cali}{m}{w}{h}$.

§.§  for the Knapsack Problem for Hyperspheres

We show now that the existence of a resource augmentation scheme for the  naturally yields a  for the problem.
This comes from the fact that in our partitioning technique, the subbins of a level are much smaller than the circles of the previous level, and this enables a good use of any empty space between the bigger circles.
This way, some guarantee of empty space between circles of level $0$ is enough to pack a big amount of bins of level $1$ onward.
To this end, the geometric characteristics of hyperspheres make it intuitive to explore the empty space in the corners of the knapsack.

Given a packing of $d$-dimensional hyperspheres with radius at least $\delta$ in a hypercuboidal bin $B$, there is an empty volume of at least $\brackets{(1 - 1/\sqrt{d}) \delta}^d$ in $B$.

Consider the bottom left corner of $B$.
Since the items are hyperspheres of radius at least $\delta$, the region delimited by this corner and a hypersphere $C$ of radius $\delta$ positioned at $(\delta, \dots, \delta)$ is surely empty.
By symmetry, the closest point of $C$ from the origin is a point $p = (a, \dots, a)$.
Then we have that $d (a - \delta)^2 = \delta^2$, which implies $a \geq \delta (1 - 1/\sqrt{d})$.
Thus, the empty hypercube of side length $a$ from the origin to $p$ gives us the desired bound on the empty volume.

This result is sufficient to obtain a  from a resource augmentation scheme.

There is a  for the knapsack problem for hyperspheres.

Let us first consider circles. Given an instance $(\cali, w, h, p)$ of the , we first obtain a gap-structured partition as in <ref>, but selecting a set of medium items $H_t$ of low profit. This way we can discard $H_t$ losing only a factor of $\eps$ of the optimal solution.

Now we obtain a super-optimal solution in an augmented knapsack of the  items as in <ref>. Since the circles of level $0$ are not scaled, no circles of $S_0$ intersect the augmented area.
Thus the resource augmentation comes from two sources: the use of scaled subbins from level $1$ onward; and the extra bins due to the rounding of the fractional balanced solution.
We show next how to handle each source of augmentation.

To remove the resource augmentation of the subbins, it is enough to consider the bins of level $1$. Since the diameter of a circle of level $1$ is at most $\eps w_1$, we can partition each subbin in $\bigO(\eps)$ strips and remove the strip of lowest profit, losing only a factor of $\eps$ in profit of the circles in the subbin, and leaving enough space to accommodate all the remaining circles in the original area of $w_1 \times w_1$.

It remains to handle the extra bins due to the rounding of the fractional solution.
From <ref> we know that the extra area $A$ that they occupy is very small, i.e., $A \leq \eps^{2rt + 2r - 5}wh$.
Also, from <ref>, we know that there is an empty area $E \geq \eps^{2\reveps t} (1 - 1/\sqrt{2})^2 w^2$ between the packed circles of $S_0$.
Thus, the empty area is much greater then the area of the extra bins, i.e, $E/A \geq \bigO(r^{2r-5})$.
Therefore, if we partition the subbins of the solution in groups of area $A$, the cheapest group surely has profit of $\bigO(\eps)$ of the total profit. Thus we replace the subbins in the augmented area by these cheapest ones and then remove the augmented space.

In all the steps we only lost factors of $\bigO(\eps)$ of the total profit, thus the final packing has profit $(1 - \bigO(\eps))$.
This extends naturally for hyperspheres.

Lastly, we can apply the procedures in <ref> to extend this result to the .

There is a  for the  with constant number of knapsacks.

§ EXTENSIONS

§.§ Area-Minimization Packing Problems

Our technique can also be applied to other packing problems, such as the ones related to the minimization of area.
One example is the  itself, in which our algorithm also yields a resource augmentation scheme with only minor changes.
The gap-structured partition and packing of the medium items work exactly the same.
Regarding the  items, we only need to adapt $\Frounded$ to solve the .
For that, it suffices to change the objective function to $\min b_0$ and constraints (<ref>) to equalities. Then <ref> works the same, leading to a resource augmentation scheme for the .
We observe that such result was already presented in <cit.>, but we show that our algorithm has the flexibility to encompass the , and with this result we can also achieve augmentation schemes for the version with demand on the items (see <ref>).

We know consider packing problems in which the objective is related to minimizing the size of a given number of bins, rather than minimizing the number of bins of a given size, such as in .
We denote one of such problems as the multiple minimum-sized bin problem. The problem is formally defined below for circles.

[Circle Multiple Minimum-size Bin Problem – ]
Given a set of circles $\cali$ and a number $m$, find the minimum value of $l$ such that $\cali$ fits in $m$ squares of side length $l$.

Hereafter we consider an instance $(\cali, m)$ of the problem and we denote by $\optMMSB{\cali}{m} := l^*$ its optimal solution.
One difference between this problem and the previous ones is that here the size of the bin is not defined a priori,
and such information is needed since the grouping made to obtain a gap-structured partition is based on the ratio between the size of the items and the size of the bin.
To handle this, we will consider a set of candidate lengths and derive a gap-structured partition for each such candidate, as follows.

First we delimit a range for these values.
For some side length $l$ to be feasible, the area of the squares must be at least the area of the circles, i.e, $m \cdot l^2 \geq \area{\cali}$. Thus, $\ubar{l} = \sqrt{\area{\cali}/m}$ is a lower bound to $l^*$.
An upper bound can be computed by encapsulating the circles in their square hulls and packing them via .
Since in a packing obtained by  all bins except the last are surely filled with a density higher than $1/4$, we have that $\area{\squarehull{\cali}} \geq (m' - 1) l^2 / 4$.
For circles, this implies that $\Bar{l} = \sqrt{32/\pi} \sqrt{\area{\cali}/m}$ is an upper bound for $l^*$.
Now we discretize the range $[\ubar{l}, \Bar{l}]$ of possible values of $l^*$ using powers of $(1 + \eps)$,
more specifically, we consider the values $\call = \set{ (1 + \eps)^k \cdot \ubar{l} : k \geq 0, (1 + \eps)^k \cdot \ubar{l} < \Bar{l} } \cup \set{ \Bar{l} }$.
We define $L = \size{\call}$ and $\Tilde{l}_i$ the $i$th smallest value present in $\call$, for $i \in [L]$.
Note that $L$ is of the order of $\log_{1 + \eps}(\Bar{l} / \ubar{l}) = \log_{1 + \eps} \sqrt{32/\pi}$, thus constant.

In possession of $\call$, we can move on to the partitioning of the instance.
We define the medium items as the set $H_t$ such that $\area{H_t} \leq 2 \eps \area{\cali}$ and $t \geq 1$, and since they are independent from the side length of the squares, they are the same for any candidate length $\Tilde{l}_i$.
On the other hand, despite the fact that the set of  items as a whole does not also depend on the side length of the bin, the partitioning of the circles into levels is dependent on it.
Thus for each $i \in [L]$ a gap-structured partition $\structsuper{\cali}{t}{i} = (S_0^i, S_1^i, \dots)$ is obtained by using the length $\Tilde{l}_i$ as the size of the bin.

Then the algorithm starts by obtaining a packing of the  items.
For that, for each $\Tilde{l}_i \in \call$, we apply the same procedure done in <ref> of scaling the circles.
Thus for each level $j$ regarding a candidate length $\Tilde{l}_i$, we obtain the feasible configurations $\calc^i_j$, the number of different sizes $T^i_j$ and demands $n_{i,j}^k$ for each $k \in [T^i_j]$.
In possession of this information, we can adapt $\Frounded$ to the  with few modifications, as shown below.
We add decision variables $y_i$ for each $i \in [L]$ that indicate whether the side length $\Tilde{l}_i$ is used. Constraint (<ref>) guarantees that only one of such sizes is used, and constraints (<ref>) ensure that only configurations related to the selected side length will be used.

(^MMSB)       $\min \quad \displaystyle \sum_{i \in [L]} \Tilde{l}_i y_i$

∑_C ∈_j^i x_j^C c_k    = n_i,j^k y_i                   ∀  i ∈[L], j ≥0, k ∈[T_j],

∑_C ∈_j^i x_j^C    = b_j^i                                  ∀  i ∈[L], j ≥0,

[r]∑_C ∈_j-1^i f_j-1(C) x_j-1^C    ≥b_j^i                   ∀  i ∈[L], j ≥1,

b_0^i    = m y_i                                                        ∀  i ∈[L],

∑_i ∈[L] y_i    = 1,

y_i    ∈               ∀  i ∈[L],

b_j^i    ∈_+                                                       ∀  j ≥0,

x_j^C    ∈_+                                                       ∀  i ∈[L], j ≥0, C ∈_j^i.

Since $L$ is bounded by a constant, we can solve the linear relaxation of $\Frounded^\mathrm{MMSB}$ maintaining the integrality of the $y$ variables and the $x_0^C$ variables for all configurations of every side length of $\call$.
Being $\Tilde{l}_j$ the optimal value of such relaxation, we have that $\Tilde{l}_j \leq \optMMSB{\cali \setminus H_t}{m} \leq \optMMSB{\cali}{m}$.
By applying the same algorithm of <ref> we obtain a packing of the level items in bins of size $(1 + \bigO(\eps)) \Tilde{l}_j := \Hat{l}$.

It remains to pack the medium items.
From the above result, we have that $\area{\cali \setminus H_t} \leq m \Hat{l}^2$, which implies that $\area{\cali} \leq \frac{1}{1 - 2\eps} m \Hat{l}^2$.
Thus, $\area{H_t} \leq 2\eps \area{\cali} \leq \frac{2\eps}{1 - 2\eps} m \Hat{l}^2 \leq 4\eps m \Hat{l}^2$ for $\eps \leq 1/4$.
Then we use the  algorithm in the same manner as in <ref> to pack $H_t$ in a strip of size $\Hat{l} \times \bigO(\eps) m \Hat{l}$,
and we apply the same procedure done for the medium items in <ref> to transform such packing into another one in $m$ strips of size $\Hat{l} \times \bigO(\eps) \Hat{l}$.
Finally, by merging the packing of the level items and the medium items we obtain a packing of $\cali$ in $m$ bins of side length $(1 + \bigO(\eps)) \Hat{l} \leq (1 + \bigO(\eps)) \optMMSB{\cali}{m}$, yielding a .

There is a  for the  problem.

A similar problem to the  is the multiple strip packing problem, formally defined next.

[Circle Multiple Strip Packing Problem – ]
Given a set of circles $\cali$, a length $w$ and a number $m$, find the minimum height $h$ such that $\cali$ fits in $m$ bins of size $w \times h$.

The only difference between  and  is that the width is fixed.
Nevertheless, we can consider a set of candidate heights in the same manner as done in , and thus we can solve the problem analogously.

There is a  for the  problem.

§.§ Packing Problems with Item Multiplicity

One problem closely related to bin packing is the cutting stock problem,where we have demand on the items.
Formally, an instance of the $d$-dimensional cutting stock problem (dCSP) is a tuple $(\cali, l, d)$ where $\cali = \{o_1,\ldots,o_n\}$ is a set of $d$-dimensional objects, $l$ is the size of a $d$-dimensional bin, and $d = (d_1,\ldots,d_n)$ is the list of demands on the objects, i.e., each object $o_i$ is associated with a positive integer demand $d_i$, for $i=1,\ldots,n$.
The two problems are very similar, but adding demand on the items actually brings more difficulty. In fact, it is not known whether the dCSP, even for $d=1,2,3$, is in NP. This arises from the fact that the size of a certifying witness may be exponential on the size of the instance (possibly in any numerical representation).
Similarly, we can also consider a version of the knapsack problem with demand on the items, and the issue with the size of a certifying witness remains. With our framework, the demand on the items is easily handled by the linear programs.
So for both problems, we can give a concise, but complete, representation of a solution: it suffices to say which bin types, and their multiplicity, are used. Formally, a description of a solution is a list $\cald$ of pairs $(B, b_B)$, where $B$ is a bin type and $b_B$ is the number of bins of type $B$ that are used in the solution. A description $\cald$ is said to be a short description if the bin types are all distinct and the size of $\cald$ (in terms of its representation in a given numerical system) is polynomially bounded on the size of the instance of the problem. In the following, we summarize the idea of building short descriptions applied to our context, and we refer to the work of Cintra et al. <cit.> for more details.

In our context, the bin types are defined over the configurations of level $0$, based on the configurations used in the other levels.
First, equal configurations are grouped together. Let $(\calb_j^1, \ldots, \calb_j^{k_j})$ the list of different groups of configurations used in level $j$, for $j \geq 0$.
At start, the description $\cald$ consists of the groups $\calb_0^{1},\ldots,\calb_0^{k_0}$, i.e., the bins only with items of level $0$. Then, the subbins of level $j$ are packed in the free space of bins from level ${j-1}$, respecting the following rules: All the subbins (of level $j$) of the same group are packed in sequence; bins (of level ${j-1}$) are opened by demand, and once opened a bin of group $\calb_{j-1}^t$, for some $1\leq t\leq k_{j-1}$, all bins of this group are used before opening new bins of group $\calb_{j-1}^{t+1}$.
Suppose we are packing subbins of group $\calb_j^{t}$ in bins of group $\calb_{j-1}^q$, for some $j \geq 1$, $1 \leq t \leq k_j$ and $1 \leq q \leq k_{j-1}$.
When the last subbin of $\calb_j^{t}$ is packed, there are three scenarios.
One, all bins of group $\calb_{j-1}^{q}$ are completely used; in this case, no new bin type is created. Two, only one bin of group $\calb_{j-1}^{q}$ is not completely used; in this case, one new bin type is created. Three, some bins of group $\calb_{j-1}^{q}$ are completely used, one is partially used and some were not opened; in this case, two new bin types are created. With simple calculations, it is possible to determine which of these scenarios happen.
Note that, for each one of the groups $\calb_j^1, \ldots, \calb_j^{k_j}$, $j \geq 1$, at most two new bin types are added in the description $\cald$. Since the number of groups is polynomial on the size of the instance, and moreover, we never create repeated types, the description $\cald$ created by this procedure is a short description of the solution given by framework.
Finally, recall that the configurations refer to the rounded objects. To obtain a description with actual objects, we use the same idea over the different sizes of objects.

It remains to give a short description of the medium objects. In the same work aforementioned, Cintra et al. <cit.> argued that any algorithm for the bin packing problem that respects some given properties, regarding grouping objects by sizes and the order in which they are packed, yields an algorithm to give a short description of a solution to the cutting stock problem. The  algorithm is one of these algorithm. Thus, it is possible to have a short description of the medium objects as well, since in our algorithm they are packed using a generalization of  algorithm to higher dimensions.

§.§ Generalizations of the Knapsack Problem

Now we show that we can actually deal with a more generalized version of the geometric knapsack problem, consisting of additional constraints on the items.
The constraints that we handle are the ones that can be expressed as linear inequalities of the form $az \leq g$ with $a \geq 0$ and $g \geq 0$, where $z$ corresponds to the decision variables that decide whether each item is packed or not.
Constraints of this type can easily model common restrictions in packing problems, such as:

* Conflict constraints: $z_i + z_j \leq 1$ for each conflict between $s_i$ and $s_j$;

* Multiple-choice constraints: $\sum_{s_i \in F} z_i \leq 1$ for each class $F$ of items;

* Capacity constraints: $\sum_{i \in [n]} w_{ji} z_i \leq W_j$ for each resource $j$.

Let $\calq = \srange{Q_1}{Q_q}$ be a set of $q$ constraints of this type.
We denote the $k$th constraint $Q_k$ by $\sum_{i \in [n]} a_{ki} z_i \leq g_k$.
Let $V = \set{z_i : i \in [n], \sum_{k \in [q]} a_{ki} > 0}$ be the set of the relevant variables present in $\calq$, with $v = \size{V}$.
We show next that if $q$ and $v$ are bounded by constants, then we can obtain an almost optimal packing respecting these constraints.

First, by choosing a set of medium items of low profit, we can simply discard them without affecting the feasibility of any original solution.
Thus, we can restrict our attention to the  items and obtain a super-optimal solution for them.
For that we can employ the same configuration IP $\Frounded$, fixing a configuration $C_0 \in \calc_0$:

([C_0])       $\max \quad \displaystyle \smashoperator[lr]{ \sum_{s_i \in \struct{\cali}{t}} } z_i \profit{i}$

(<ref>)   –(<ref>),

x_0^C_0    = 1,

∑_i ∈[n] a_ki z_i    ≤g_k                                              ∀  k ∈[q].

We want to decompose the IP in blocks in the same manner as explained in <ref>.
For that, we first obtain an optimal fractional solution $\Tilde{Z} = (\Tilde{x}, \Tilde{b}, \Tilde{z})$ of the linear relaxation of $\Frounded$ but maintaining the integrality of the variables in $V$. Since $v \in \bigO(1)$, we can do this in polynomial time.
Now consider a constraint $Q_k$.
We have that $\sum_{i=1}^n a_{ki} \Tilde{z_i} = \Tilde{g}_k$ for some $\Tilde{g}_k \leq g_k$.
We partition the left-hand sum of the equation based on the items of each level, as follows.
For each level $j$, let $\Tilde{g}_{kj} = \sum_{i \in [n] : s_i \in S_j} a_{ki} \Tilde{z}_i$.
Then we replace the constraint $Q_k$ by the set of constraints

\begin{equation} \label{eq:gkj}
\sum_{i \in [n]: s_i \in S_j} a_{ki} z_i = \Tilde{g}_{kj} \quad \forall\, j \geq 0.
\end{equation}

With this replacement and using the fractional solution $\Tilde{Z}$, we can obtain an IP where all the constraints indexed by a level $j$ have only variables $x$, $z$ and $b$ of the corresponding level.
Thus we can decompose it in blocks where each block corresponds to a subproblem for each level.
Namely, the $j$th block is given by the formulation $\Flevel[j]$ described below.

[][j]       $\max \quad \displaystyle \sum_{s_i \in S_j} z_i \profit{i}$

(<ref>), (<ref>)   , (<ref>),(<ref>),

∑_C ∈_j x_j^C    = ∑_C ∈_j x_j^C,

[r]∑_C ∈_j f_j(C) x_j^C    = b_j+1,

[r]∑_i ∈[n]: s_i ∈S_j a_ki z_i    = g_kj                                ∀  k ∈[q].

In possession of this decomposition, we can obtain an optimal solution $(x_j^*, z_j^*)$ for each level by solving $\Flevel[j]$ individually, still maintaining the integrality of the associated variables in $V$, and then merge the solutions to obtain an optimal fractional solution $(x^*, z^*, b^*)$ for the entire problem.
Such solution is feasible, since for each constraint $Q_k$ we have that

\begin{equation*}
\sum_{i \in [n]} a_{ki} z^*_i = \sum_{j \geq 0} \sum_{i \in [n]: s_i \in S_j} a_{ki} z^*_i = \sum_{j \geq 0} \Tilde{g}_{kj} = \Tilde{g}_k \leq g_k.
\end{equation*}

Furthermore, $\Flevel[j]$ has $\bigO(T_j + q)$ constraints. By making $\eps \leq 1/q$, we have that $T_j + q \leq \reveps^3 \ln(\reveps) + \reveps = \bigO(\reveps^3 \ln(\reveps))$.
Thus the number of fractional variables in each level is bounded by the same order as in <ref>.
Also, since we maintained the integrality constraints of all the variables in $V$, we know that all the $z_i$ variables presented in $\calq$ have integer values, and therefore any rounding does not affect these values, and consequently does not interfere in the feasibility of the constraints $\calq$.
Hence, we can apply the same algorithm in <ref> to obtain a super-optimal solution for the  items. This leads to the following.

Let $\cali$ be an instance of the geometric multiple knapsack problem with added constraints $\calq$ of the form $az \leq g$ with $a \geq 0$ and $g \geq 0$, and let $V = \set{z_i : i \in [n], \sum_{k \in [q]} a_{ki} > 0}$. If $\size{\calq} \in \bigO(1)$ and $\size{V} \in \bigO(1)$, then if the items are convex fat objects there is a  under resource augmentation. If the items are hyperspheres, then the resource augmentation is only due to numerical precision in the representation of irrational numbers.

§ GENERALIZATION TO FAT OBJECTS

The resource augmentation scheme we presented in <ref> for circles can be generalized to convex $d$-dimensional fat objects.
Moreover, if the objects attend a special condition, then we can even restrict the resource augmentation to only one dimension (as in <ref>).

We define a fat object by the concept of two-ball fatness.
For an object $o$, we denote by $\fatd{o}$ and $\fatD{o}$ the radii of the inscribed and circumscribed spheres of $o$, respectively. We say that $o$ is a $\psi$ object if $\fatD{o}/\fatd{o} \leq \psi$, for some constant $\psi \geq 1$.
From all the possible inscribed spheres of $o$, in a packing, we always consider the one whose center is closest to the origin. The position of $o$ is given by the coordinates of the center of its inscribed sphere.

For our framework to work, we need to ensure the following:

$i)$ there is a polynomial-time algorithm to decide if a set of objects can be packed in a given bin, and if so, it returns a packing of the objects in an augmented bin (possibly in all dimensions);

$ii)$ only a small amount of volume is wasted due to the (discarded) subbins of the subsequent level that partially intersects an object.

The second requirement is easily guaranteed with our technique, since it allows us to calibrate the granularity of the gap-structured partition, so ensuring that the subbins of a level are sufficiently much smaller than the items of the previous level. This way, we can ensure that the total volume of the bins of a level $j$ that partially intersect objects of level $j-1$ is sufficiently small.

As for the first requirement, to obtain such algorithm, we use the same algebraic apparatus employed for circles. This turns out to bring great versatility on the objects covered by our framework.
Essentially, it must be possible to describe the object by a system of polynomials. To ensure polynomial time, the system must have a constant number of equalities and inequalities.
However, in case this is not true, we can approximate the object to a new one attending this requirement. To achieve that, we draw a grid consisting of hypercubes of small (constant) side length $\delta$ over the object, and obtain the convex hull of all the cells of the grid that partially intersect the object. We observe that any point in the convex hull is at a distance at most $\sqrt{d}\delta$ from the boundary of the original object. Then, it suffices to take a small enough value of $\delta$ so that the increase in volume, between the original and the new objects, is not significant. For instance, setting $\delta = \eps/d$ guarantees a distance of at most $\bigO(\eps)$.

The maximum number of cells that gave origin to the convex hull of the approximate object is limited by the volume of the bin over the the volume of the grid cell, which is constant assuming the size of the bin is constant. Then, the convex hull can be described by a constant number of curves, as desired.

Finally, we remark that our framework supports a wide range of objects also for the bins. Akin to the items, it must be a convex object and it must be described by a system of polynomials.
We observe that the shape of the bin affects the computation of a packing only in the first level, because from level $1$ onward, the objects are packed in hypercubes again due to the use of the grid partition strategy.

§.§ Resource Augmentation Scheme

Let $(\cali, l, \profit{})$ be an instance of the knapsack problem for $d$-dimensional fat objects, which we refer to as , where $\cali$ is an input set of $\psi$ objects, $l = (l_1,\ldots,l_d)$ is the size of a knapsack $B$, and $p$ is a function of profit on the objects.
Without loss of generality, we assume $l_{\min} = l_1 \leq \ldots \leq l_d = l_{\max}$.

We present the necessary adaptations to what was presented in <ref>.
Recall that, in short, our resource augmentation scheme consists of three main steps: obtaining a gap-structured partition, packing the medium items, and packing the level items.

Gap-structured partition.
To obtain a gap-structured partition, we classify the items based on the diameter of the objects' circumscribed spheres and the smallest side of the $d$-dimensional bin.
We define groups $G_i = \set{o_j \in \cali : \eps^{\reveps{}i} l_{\min} \geq 2\fatD{o} > \eps^{\reveps{}(i+1)}}$.
Similarly as before, we choose the medium items as follows. Let $I^* \subseteq \cali$ be the set of objects of an optimal solution. For some $1 \leq t < \reveps$, there must be a set $H_t$ such that $\vol{H_t \cap I^*} \leq \frac{1}{(\reveps - 1)} \vol{B} \leq 2 \eps \vol{B}$. Again, we fix such index $t$ and handle the medium items $H_t$ separately, by packing a high-profit subset of $H_t$ in a strip of small height.
Based on such index $t$, we define the  objects, denoted $\struct{\cali}{t}$, as the sets $S_j = \bigcup_{i = t + (j-1)\reveps + 1}^{t + j\reveps - 1} G_i$, for $j \geq 0$.
We denote by $\fatD{\min}^j$ and $\fatD{\max}^{j}$ the radii of the circumscribed spheres of the smallest and largest objects in $S_j$, respectively.

Packing  objects.
We proceed to the packing of the  objects.
The objects of $S_0$ are packed in $B$, and
for $j \geq 1$, we set $w_j = \eps^{\reveps(t + (j-1)\reveps) + \reveps - 1} l_{\min}$, representing the side length of hypercubes (subbins) used to pack the items from level $1$ onward, in their respective levels.
To pack the  items, we need a bound on the number of different object patterns (equivalent to different radii for circles) in each level. To this end, we round up the radius of the objects' circumscribed spheres to powers of $1+\eps$, and scale each point of the object accordingly.

Let $R_j = \set{ \fatD{\min}^j(1 + \eps)^k : k \geq 0, \fatD{\min}^j(1 + \eps)^k < \fatD{\max}^j } \cup \set{\fatD{\max}^j}$.
For each level $j$, we round up the radius of the circumscribed spheres of the objects of $S_j$ to the closest value in $R_j$.
We refer to the objects after the rounding as scaled objects.
By <ref>, the number of different patterns in each level is $T_j \leq \reveps^3 \ln{r}$.
Since the number of different patterns is now constant, we have a good bound on the number of configurations in each level.

For any level $j$, the number of different configurations of scaled objects of $S_j$ is bounded by a constant.

To estimate the number of objects that fit in a bin, we use the volume of the hypercube inscribed with a hypersphere of radius $\fatD{\min}^{j}/\psi$ (i.e., the smallest possible inscribed sphere among the scaled objects of $S_j$), which has side length $\frac{2\fatD{\min}^j}{\psi\sqrt{d}}$.

We estimate level $0$ first. The maximum number of scaled objects of $S_0$ that fit in the knapsack is bounded by

\begin{align*}
M_0 &\leq \frac{\vol{B}}{\paren*{\frac{2 \fatD{\min}^{0}}{\psi \sqrt{d}}}^d} \\
&\leq \paren*{\frac{\psi\sqrt{d}}{2}}^d \frac{{l_{\max}}^d}{(\eps^{rt} \ l_{\min})^d} \\
&\leq \paren*{\frac{\psi\sqrt{d}}{2} \frac{l_{\max}}{l_{\min}}}^d \ \eps^{dr} \quad \text{(since $t \geq 1$)} \\
\end{align*}

Since a configuration of $S_0$ is composed of $T_0$ values, and each value can range from $0$ to $M_0$, the total number of possible configurations of level $0$ is at most

\begin{equation*}
(M_0+1)^{T_0} \leq \paren*{\paren*{\frac{\psi\sqrt{d}}{2} \frac{l_{\max}}{l_{\min}}}^d \ \eps^{dr}  \ + \ 1}^{\reveps^3 \ln{r}},
\end{equation*}

which is constant under the assumption that both $l_{\max}/l_{\min}$ and $d$ are constants.

For levels $j \geq 1$, the maximum number of objects that fit in a bin is bounded by

\begin{align*}
M &\leq \frac{{w_{j}}^d}{\paren*{\frac{2 \fatD{\min}^{j}}{\psi \sqrt{d}}}^d} \\
&= \paren*{\frac{\psi\sqrt{d}}{2}}^d \ \frac{(\eps^{\reveps(t + (j-1)\reveps) + \reveps - 1} l_{\min})^d}{(\eps^{r(t + j\reveps)} l_{\min})^d} \\
&= \paren*{\frac{\psi\sqrt{d}}{2}}^d \ \reveps^{d(\reveps(\reveps-1)+1)}.
\end{align*}

Again, since a configuration is composed of $T_j$ values, each value ranging from $0$ to $M$, for $j\geq 1$, the total number of possible configurations in each level $j\geq 0$ is at most

\begin{equation*}
(M+1)^{T_j} \leq \paren*{\paren*{\frac{\psi\sqrt{d}}{2}}^d \ \reveps^{d\reveps(\reveps-1)+1} \ + \ 1}^{ \reveps^3 \ln{r} },
\end{equation*}

which is constant under the assumption that $d$ is constant.

Since the number of configurations, in each level, is constant, we can use the algorithm based on configuration IPs, still in polynomial time.
The feasibility of a configuration is checked using a generalization of the algebraic apparatus to $d$-dimensions. The formulations of the linear programs are the same. For simplicity, we refer to them with the same names as before.

It remains to show that the extra bins due to the rounding of a fractional solution fit in a small $d$-dimensional strip.
Recall that in level $0$ there is no extra bins, since the variables $x_0$ are integers, and that in each level $j\geq 1$, the number of extra bins is limited by the number of restrictions of the IP $\Flevel$, which in turn, is bounded by $\bigO(T_j)$ (the number of different patterns in level $j$).

Let $(x^*, b^*, z^*)$ be an optimal balanced fractional solution of $\milpFrounded$ for an instance $(\cali, l, \profit{})$ of the .
The extra bins created after rounding the variables $x^*$ to $\ceil{x^*}$ fit into a $d$-dimensional strip of size $(l_1, l_2, \ldots, \eps l_d)$.

We know from <ref> that the number of rounded $x_j$ variables is at most $2T_j + 2$, for each $j\geq 1$.
From <ref>, which still holds for $d$-dimensional fat objects, we have $T_j \leq \reveps^3 \ln{\reveps}$.

\begin{equation*}
2T_j + 2 \leq 2\reveps^3\ln(\reveps) + 2.
\end{equation*}

The number of bins of level $1$ that fits in a strip of size $(l_1, l_2, \ldots, \eps l_d)$ is bounded by

\begin{align*}
\frac{\eps l_{\max} \prod_{i=1}^{d-1} l_i  }{w_1^d}
&\geq \frac{\eps {l_{\min}}^d}{\eps^{d(2\reveps-1)} {l_{\min}}^d} & \text{(since $t \geq 1$)} \\
&\geq \reveps^{d(2\reveps-1)-1} & \\
&\geq \reveps^{13} & \text{(since $\reveps \geq 4$ and $d\geq2$)} \\
&\geq 2\reveps^3\ln(\reveps) + 3.
\end{align*}

This means that the strip is sufficiently large to accommodate all extra bins of level $1$, still leaving room for at least one more bin of level $1$.
Now we show that for $j \geq 2$, one bin of level $j-1$ is sufficient to accommodate the extra bins of level $j$, still leaving room for at least one more bin of level $j$.
The result follows from direct calculation.

\begin{align*}
\frac{{w_{j-1}}^d}{w_j^d} &\geq \frac{\eps^{d(\reveps(t + (j-2)\reveps) + \reveps - 1)} {l_{\min}}^d} {\eps^{d(\reveps(t + (j-1)\reveps) + \reveps - 1)} {l_{\min}}^d} & \\
&\geq \reveps^{d\reveps^2} & \\
&\geq r^{32} & \text{(since $\reveps \geq 4$ and $d\geq2$)} \\
&\geq 2\reveps^3\ln(\reveps) + 3.
\end{align*}

Since after packing the extra bins of level $1$ there is still space for at least one free bin of level $1$, and for level $j \geq 2$, one bin of level ${j-1}$ is sufficient to pack all the extra bins plus one of level $j$, we conclude that all the extra bins of every level fit into a strip of size $(l_1, l_2, \ldots, \eps l_d)$.

Packing the medium objects.
To pack the medium objects, the idea is the same explained for circles. We circumscribe the objects in hypercubes and apply a generalization of the  algorithm to $d$ dimensions.

First, we show that the volume of an object is at least a constant of the volume of its circumscribed hypercube.
Let $o$ and $\squarehull{o}$ be a $\psi$ object and its circumscribed hypercube, respectively. Let $V_o$ and $\squarehull{V_o}$ be the volume of $o$ and $\squarehull{o}$, respectively. The following lemma gives us the ratio between the volume of $o$ and $\squarehull{o}$.

For any $d$-dimensional $\psi$ object $o$, it holds that $\squarehull{V_o} / V_o \leq 2^{\frac{d}{2}} \psi^d$.

Let $V$ be the volume of the $d$-dimensional unit sphere.
Denote by $V_k$ the volume of a $d$-dimensional sphere of diameter $k$.
We start with the following fact.

Fact. The volume of a $d$-dimensional sphere of diameter $k$ is $(k/2)^d V$.

Observe that the hypercube $\squarehull{o}$ is circumscribed by a sphere of diameter $ k = \sqrt{2}\fatD{o}$.

\begin{align*}
\frac{\squarehull{V_o}}{V_o} &\leq \frac{V_{k}}{V_{\fatd{o}}} \\
&= \frac{(k/2)^d V}{(\fatd{o}/2)^d V} \\
&= \frac{(\sqrt{2}\fatD{o}/2)^d V}{(\fatd{o}/2)^d V}\\
&= 2^{\frac{d}{2}} \psi^d.
\end{align*}

Now, we use the same idea of <ref> to obtain a high-profit packing of $H_t$.
With the result of <ref> combined with the guarantees of filled volume by  (<ref>), we know that  can fill a volume at least as big as that used by the medium objects of an optimal solution. Due to the ordering of the objects by relative value in <ref>, the profit of the packed objects is at least that of the medium objects of an optimal solution, as desired.

This settles the medium items. Then, we can enunciate the final result.

There is a resource augmentation scheme for the multiple knapsack problem of convex fat objects.

Finally, we observe that, when the objects have a lifting property, the resource augmentation can be restricted to only one dimension.
Essentially, this property consists in being possible to rearrange the objects within the bin, by slights shifts in a way that only the height of the bin is increased.

For the objects that do not present such property, we cannot use the algebraic apparatus to obtain a packing from a configuration.
In such cases, we can use some algorithm based on discretization to pack the objects into one bin; however, the resource augmentation is in all dimensions.
One algorithm of this nature was presented by Bansal et al. <cit.> for packing hypercubes into the minimum number of unit bins.
At last, we observe that although a discretization approach could also be applied for objects with the lifting property, the algebraic approach gives a better time complexity.

§.§ Resource Augmentation Scheme with Rotation

In this section, we show that our technique can be improved to allow rotation on the items. In this case, the resource augmentation is in all dimensions.
Here the items are $d$-dimensional fat objects that meet the criteria described in Subsection <ref>.
We consider a $d$-dimensional bin of size $(l_1,\ldots,l_d)$.
When the context is sufficient to rule out ambiguity, we write simply bin for a $d$-dimensional bin and simply object for a $d$-dimensional object.

Given that, in a $d$-dimensional space, the number of rotational degree of freedom of an object is $\binom{d}{2}$, we define a rotation as a tuple $\alpha = (\alpha_{\scaleto{11\mathstrut}{6pt}},\alpha_{12},\ldots,\alpha_{1d},\alpha_{22},\alpha_{23},\ldots,\alpha_{2d},\alpha_{33},\ldots,\alpha_{dd})$, where each $\alpha_{ij}$ is an angle associated with the $ij$-plane.
Then, to rotate an object $o$ by a rotation $\alpha = (\alpha_{11},\ldots,\alpha_{dd})$ means rotating $o$ in each $ij$-plane by the angle $\alpha_{ij}$, for $1 \leq i < j \leq d$.
We say that a rotation $\alpha$ respects an angle $\theta$ if every $\alpha_{ij}$ is a multiple of $\theta$.
We extend the term and say that a packing respects an angle $\theta$ if every packed object assumes a rotation that respects $\theta$.
We define the center of the inscribed sphere of an object as the point of reference for any rotation. We suppose that rotations are always clockwise and we consider the $\arccos$ function restricted to the interval $[0,\pi]$.

First, we show that given a set $\cali$ of objects and a packing $P$ of $\cali$ in a bin $B$, there exists another packing $P'$ of $\cali$ in an augmented bin $B'$ such that every object is rotated by a rotation that respects a certain angle $\alpha$, and $B'$ is augmented in all dimensions by a factor of a positive constant.

For that purpose, we show that we can scatter the objects in $P$ in a strategic way so that we create some extra space between any two objects, without introducing overlaps.
The downside is that this procedure requires resource augmentation in all dimensions of the bin.
Once we have the objects scattered, we show that this extra space is sufficient to rearrange the objects so that all of them reach a rotation that respects an angle $\alpha$ to be defined later.
The following lemma regards the scattering procedure.

Consider a set $\cali$ of objects with $\fatd{o} \geq \gamma$, for every $o\in\cali$, and some constant $\gamma > 0$.
Let $P$ be a packing of $\cali$ in a $d$-dimensional bin and $\delta>0$ be a constant.
Then, there is a packing of $\cali$ where the distance between any two objects is at least $\delta / \sqrt{d}$, and the bin is augmented by at most $\delta(l_k/\gamma)$ in each dimension $k \in [d]$.

We consider $d$ sequences $S_1,\ldots,S_d$, where $S_i=(o_{i1},\ldots,o_{in})$ is a sequence of the objects, such that, for every dimension $i$, we can shift, in the increasing direction of the axis, object $o_{ij}$ before $o_{i(j+1)}$ by $\delta$ units, for $i=1,\ldots,d$ and $j=1,\ldots,n$, in a way that the space between the objects only increases. We do the shifting in every dimension, starting with $i=1$ until $i=d$.

To estimate the new distance between any two objects, we take two arbitrary objects $A$ and $B$ in the packing $P$. By convexity, there exists a hyperplane $H$ separating them.
When we apply the shifting procedure over $P$, the hyperplane $H$ is shifted as well. Let $H'$ be the equivalent of hyperplane $H$ after the shifting.
Note that the distance between $A$ and $B$ is at least the distance between $H$ and $H'$.
Then, it suffices to measure a $d$-dimensional vector $\va{v} = \va{v}_1 + \ldots + \va{v}_d$ orthogonal to both $H$ and $H'$.
We denote by $\theta_i$ the angle between $\va{v}$ and its component in the $i$-th dimension $\va{v}_i$, for $i=1,\ldots,d$.

Consider vectors $\va{\delta}_1, \ldots, \va{\delta}_d$ where for each $\va{\delta}_i = (\delta_{i1},\ldots,\delta_{id})$, we have $\delta_{ii} = \delta$ and $\delta_{ij} = 0$, for $j \neq i$, $i=1,\ldots,d$.
Let $\mathtt{proj}_{\mathbf{v}}\ \va{\delta}_i$ be the projection of vector $\va{\delta}_i$ in vector $\va{v}$.
For every $i=1,\ldots,d$, it holds that $\|\va{v}\| \geq \|\mathtt{proj}_{\mathbf{v}}\ \va{\delta}_i\|$.
From the fact that, for any vector $\va{v}$, the squares of the cosines of all $\theta_i$ add up to one, we have that there is one $j$ such that $\cos{\theta_j} \leq 1/\sqrt{d}$.

We then conclude that the space between $A$ and $B$ in each dimension is at least

\begin{align*}
\|\va{v}\| &\geq \|\mathtt{proj}_{\mathbf{v}}\ \va{\delta}_i\| \\
&= \|\va{\delta}_j\| \cos{\theta_j} \\
&= \delta \cos{\theta_j} \\
&\geq \frac{\delta}{\sqrt{d}}.
\end{align*}

It remains to argue the increase of the bin. For any dimension $k$, the number of objects that fit in the $k$-th dimension of the bin is $N_k \leq \floor{l_k / \gamma}$. Then the total increase in each dimension $k$ is $\delta N_k \leq \delta (l_k/\gamma)$, for $k=1,\ldots,d$.

Provided with the extra space we can rearrange the objects so that they attend the desired conditions, i.e., they are all rotated by a rotation that respects a certain angle $\alpha$ to be defined later.

We denote by $\proj{ij}{o}$ the projection of an object $o$ in the $ij$-plane.
The $\border{\lambda}{}$ of an object $o$ is defined as follows: For each $ij$-plane, $1 \leq i < j \leq d$, we position the center of a circle of radius $\lambda$ in one point of the boundary of $\proj{ij}{o}$ and run this circle along all the boundary of $\proj{ij}{o}$. When restricted to some $ij$-plane, we write $\border{\lambda}{ij}$ of $o$.
The next lemma gives bounds on the value of the angle $\alpha$ by which an object can be rotated in each $ij$-plane.

For any $1\leq i < j \leq d$, a $\psi$ object $o$ can be rotated in the $ij$-plane by an angle $\alpha_{ij}$ without violating its $\border{\lambda}{ij}$, with $\theta \leq \alpha_{ij} \leq \theta+\pi$ and $\theta = \arccos{\left(1 - \frac{\lambda^2}{8{\fatD{o}}^2} \right)}$.

Consider the projection $\proj{ij}{o}$ of $o$ in some $ij$-plane, with $1 \leq i < j \leq d$, and let $c$ be the center of its inscribed circle.
Let $R$ be the length of the longest line segment starting in $c$ and ending in some point $q$ of the boundary of $\proj{ij}{o}$.
Let $\alpha_{ij}$ be the angle by which we can rotate $o$ in the $ij$-plane until $q$ hits a point $q'$ in the $\border{\lambda}{ij}$ of $o$.
We call $x$ the distance between $q$ and $q'$.
Note that the line segment from $c$ to $q'$ also has length $R$ and that $x \geq \lambda$.

Consider the isosceles triangle with two sides of length $R$, defining the angle $\alpha_{ij}$, and one side of length $x$.
By law of cosines, we have

\begin{align*}
\cos{\alpha_{ij}} &= 1 - \frac{x^2}{2R^2} \\
&\leq 1 - \frac{\lambda^2}{2(2\fatD{o})^2} \\
&\leq 1 - \frac{\lambda^2}{8{\fatD{o}}^2} \\
\end{align*}

Thus, taking $\theta = \arccos{\left(1 - \frac{\lambda^2}{8{\fatD{o}}^2} \right)}$, we have $\theta \leq \alpha_{ij} \leq \theta+\pi$.

We can now enunciate the theorem that assures the existence of the modified packing we desire.
Recall that for a $\psi$ object $o$, we denote by $\fatd{o}$ and $\fatD{o}$ the diameters of the inscribed and circumscribed spheres of $o$, respectively.

Let $\gamma>0$ be a constant and $\cali$ be a set of $d$-dimensional $\psi$ objects, with $\fatd{o} \geq \gamma$ for every $o \in \cali$.
Consider a packing $P$ of $\cali$ in a $d$-dimensional bin.
For any $\eps>0$, there exists another packing $P'$ of $\cali$ where the bin is augmented in all dimensions by a factor of $\eps$ and each object $o$ has a rotation that respects $\arccos{\left(1 - \frac{\eps^2}{32 d \psi^2} \right)}$.

Let $P'$ be a packing obtained by applying the shifting procedure from <ref> over $P$ with $\delta = \eps\gamma$. Then, in the new packing $P'$, the bin is augmented by $\eps l_k$
in each dimension $k$, and there is a space of
${\eps\gamma}/{\sqrt{d}}$ between any two objects.

Given the space between the objects, we draw a $\border{\lambda}{}$, with $\lambda = {\eps\gamma}/{2\sqrt{d}}$, around each object in $P'$.
By <ref>, we can rotate each object $o$ in each $ij$-plane by

\begin{align*}
\alpha &\geq \arccos{\left(1 - \frac{\lambda^2}{8{\fatD{o}}^2} \right)} \\
&= \arccos{\left(1 - \frac{\eps^2 \gamma^2}{32 d {\fatD{o}}^2} \right)} \\
&\geq \arccos{\left(1 - \frac{\eps^2}{32 d \psi^2} \right)}, \\
\end{align*}

where the last inequality comes from the assumptions that the objects are $\psi$ and $\fatd{o}\geq\gamma$, for every object $o\in\cali$.

Since each object $o$ can be rotated by angles of at most $\arccos{\left(1 - \frac{\eps^2}{32 d \psi^2} \right)}$, we can always obtain a rotation of $o$ that respects $\arccos{\left(1 - \frac{\eps^2}{32 d \psi^2} \right)}$.

So far, we showed that, given a set $\cali$ of objects, a packing $P$ of $\cali$ in a bin $B$ of size $(l_1,\ldots,l_d)$ and a constant $\eps > 0$, there exists another packing $P'$ of $\cali$ in a bin augmented by $\eps l_k$ in the $k$-th dimension, $1 \leq k \leq d$, such that every object is rotated by a rotation that respects the angle $\alpha = \arccos{\left(1 - \frac{\eps^2}{32 d \psi^2} \right)}$.

To obtain a packing such as $P'$, we use our framework with an increment to cover the rotation on the objects.
The idea is to account for the possible rotations an object can assume along with the configurations.
Again, to decide if a given a set of objects can be packed in a bin, we use that algorithm based on algebraic apparatus.
However, for each configuration, we first fix one rotation for each object, then we apply that algorithm. If a configuration is feasible under some combination of rotations of its objects, it suffices to find one.

We already know that, for each level $j\geq 0$, the number of configurations (for that level) is bounded by a constant.
Then, it suffices to have a constant bound on the number of rotations an object can assume.
First, we discretize the range $[0,2\pi]$ into a set $A = \{0, \alpha, 2\alpha, 3\alpha, \ldots, K\alpha\}$, with $K = \floor{2\pi/\alpha}$, of multiples of $\alpha$.
Since a rotation is composed of $\binom{d}{2}$ values, each assuming a value from $A$, the number of possible rotations that respects $\alpha$ is bounded by $|A|^{\binom{d}{2}}$, which is constant.

Finally, the medium objects are handled in the same way.
The difference here is that, for each object $o$, instead of considering the hypercube circumscribed with the object's circumscribed sphere, we consider the hypercube circumscribed with a sphere of diameter $2\gamma\fatD{o}$, i.e., the circumscribed sphere and its $\gamma$-border. This way, each object can be rotated to assume a rotation that respects $\alpha$ without surpassing the boundaries of its respective hypercube.

§ FINAL REMARKS

Geometric packing problems have been investigated for centuries in mathematics. A great example is the Kepler's conjecture for the packing density of $3$-dimensional spheres in the Euclidean space.
In contrast, we do not find so many works on sphere packing in the field of approximation algorithms. Most results are for squares and rectangles, and their $d$-dimensional counterparts.
To help filling this gap, in this work we presented a framework suitable to obtain good approximation results for several geometric knapsack and packing problems, such as the multiple knapsack problem, the multiple strip packing problem and the multiple minimum-size bin problem, supporting not only hyperspheres but also many other different geometric objects, both for the items and bins. Moreover, our framework easily supports demand on the items (for instance, as in the cutting stock problem).

We showed a resource augmentation scheme for the hypersphere knapsack problem that naturally turns into a , given our fine-grained partitioning of the items in levels and the sparsity of sphere packing. Moreover, our  also naturally extends to the multiple knapsack problem with constant number of knapsacks.
In addition, for a wide range of convex fat objects, we devised a resource augmentation scheme.
In some cases, our resource augmentation is restricted to only one dimension.