$\bar{\lambda}=\frac{1}{2}\cdot\bar{\phi}+\frac{1}{2}\cdot\bar{\phi}^{\prime}$,
and we conclude that $\bar{\lambda}$ is not a vertex of the
$\bar{x}$-polytope. Contradiction. ∎

######  Lemma B.4.

If a group $G\in{\mathcal{G}}$ is fractional, then

$|\\{\bar{\lambda}_{\ell,t}\in(0,1)~{}|~{}\ell\in G,t\in T\\}|\leq 2|T|.$

###### Proof.

Let $X=\\{(\ell,t)\in G\times T~{}|~{}\ell\notin\textsf{fit}(t)\\}$. Define
$R=G\times T\setminus X$ as the set of all pairs of items where the first fits
in the place of the second. Let $Q\subseteq\mathbb{R}^{R}$ be the set
(polytope) of all the vectors $\bar{\rho}\in\mathbb{R}^{R}$ which satisfy the
following constraints:

$\displaystyle\displaystyle\bar{\rho}_{\ell,t}\geq
0~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}\forall(\ell,t)\in
R~{}~{}~{}~{}~{}~{}~{}$ (46)
$\displaystyle\rule{0.0pt}{18.00005pt}\displaystyle\sum_{t\in T\text{ s.t.
}(\ell,t)\in R}\bar{\rho}_{\ell,t}\geq
1~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}\forall\ell\in
G~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}$ (47)
$\displaystyle\rule{0.0pt}{18.00005pt}\displaystyle\sum_{\ell\in G\text{ s.t.
}(\ell,t)\in R}\bar{\rho}_{\ell,C}\cdot s(\ell)+\sum_{\ell\in I\setminus
G}\bar{\lambda}_{\ell,C}\cdot
s(\ell)\leq(1-s(C))\bar{x}_{C}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}\forall
C\in{\mathcal{C}}\cap T~{}~{}~{}~{}~{}~{}$ (48)
$\displaystyle\rule{0.0pt}{18.00005pt}\displaystyle\sum_{\ell\in G\text{ s.t.
}(\ell,t)\in R}\bar{\rho}_{\ell,t}\leq
L_{t,G}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}\forall
t\in T~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}$ (49)

Now, we define $\bar{\phi}\in\mathbb{R}^{R}$ by
$\bar{\phi}_{\ell,t}=\bar{\lambda}_{\ell,t}$ for all $(\ell,t)\in R$. As
$\bar{\lambda}$ belongs to the $\bar{x}$-polytope, it easily follows that
$\bar{\phi}\in Q$ since $\bar{\lambda}_{\ell,t}=0$ for all
$(\ell,t)\in(I\times I\cup{\mathcal{C}})\setminus R$ by (4) (i.e., where
$\ell\notin\textsf{fit}(t)$).

######  Claim B.5.

$\bar{\phi}$ is a vertex of $Q$.

###### Proof.

Assume towards contradiction that $\bar{\phi}$ is not a vertex of $Q$. Thus,
there is a vector $\bar{\gamma}\in\mathbb{R}^{R}$, $\bar{\gamma}\neq 0$ such
that $\bar{\phi}+\bar{\gamma},\bar{\phi}-\bar{\gamma}\in Q$. Thus, by (47),
for all $\ell\in G$ we get that

$1\leq\sum_{t\in T\text{ s.t. }(\ell,t)\in
R}(\bar{\phi}_{\ell,t}+\bar{\gamma}_{\ell,t})=\sum_{t\in T\text{ s.t.
}(\ell,t)\in R}\bar{\phi}_{\ell,t}+\sum_{t\in T\text{ s.t. }(\ell,t)\in
R}\bar{\gamma}_{\ell,t}=1+\sum_{t\in T\text{ s.t. }(\ell,t)\in
R}\bar{\gamma}_{\ell,t}$

The last equality is because $\bar{\lambda}$ satisfies constraint (8) of the
$\bar{x}$-polytope with equality and by the definition of $\phi$. In addition,

$1\leq\sum_{t\in T\text{ s.t. }(\ell,t)\in
R}(\bar{\phi}_{\ell,t}-\bar{\gamma}_{\ell,t})=\sum_{t\in T\text{ s.t.
}(\ell,t)\in R}\bar{\phi}_{\ell,t}-\sum_{t\in T\text{ s.t. }(\ell,t)\in
R}\bar{\gamma}_{\ell,t}=1-\sum_{t\in T\text{ s.t. }(\ell,t)\in
R}\bar{\gamma}_{\ell,t}$

The last equality is because $\bar{\lambda}$ satisfies constraint (8) of the
$\bar{x}$-polytope with equality and by the definition of $\phi$. Hence, by
the above it follows that

$\sum_{t\in T\text{ s.t. }(\ell,t)\in R}\bar{\gamma}_{\ell,t}=0.$ (50)

Furthermore, for all $t\in T$ the following hold by (49):

$L_{t,G}\geq\sum_{\ell\in G\text{ s.t. }(\ell,t)\in
R}(\bar{\phi}_{\ell,t}+\bar{\gamma}_{\ell,t})=\sum_{\ell\in G\text{ s.t.
}(\ell,t)\in R}\bar{\phi}_{\ell,t}+\sum_{\ell\in G\text{ s.t. }(\ell,t)\in
R}\bar{\gamma}_{\ell,t}$

and

$L_{t,G}\geq\sum_{\ell\in G\text{ s.t. }(\ell,t)\in
R}(\bar{\phi}_{\ell,t}-\bar{\gamma}_{\ell,t})=\sum_{\ell\in G\text{ s.t.
}(\ell,t)\in R}\bar{\phi}_{\ell,t}-\sum_{\ell\in G\text{ s.t. }(\ell,t)\in
R}\bar{\gamma}_{\ell,t}$

Hence, by the above, because for all $(\ell,t)\in R$ it holds that
$\bar{\lambda}_{\ell,t}=\bar{\phi}_{\ell,t}$, and that by (4) for all
$(\ell,t)\notin R$ it holds that $\bar{\lambda}_{\ell,t}=0$, for all $t\in T$
it follows that:

$\sum_{\ell\in G}\bar{\lambda}_{\ell,t}-L_{t,G}\leq\sum_{\ell\in G\text{ s.t.
}(\ell,t)\in R}\bar{\gamma}_{\ell,t}\leq L_{t,G}-\sum_{\ell\in
G}\bar{\lambda}_{\ell,t}.$ (51)

Define
$\bar{\lambda}^{+},\bar{\lambda}^{-}\in\mathbb{R}^{I\times(I\cup\mathcal{C})}$
by
$\bar{\lambda}^{+}_{\ell,t}=\bar{\lambda}^{-}_{\ell,t}=\bar{\lambda}_{\ell,t}$
for $(\ell,t)\in\left(I\times(I\cup\mathcal{C})\right)\setminus R$, and
$\bar{\lambda}^{+}_{\ell,t}=\bar{\lambda}_{\ell,t}+\bar{\gamma}_{\ell,t},~{}\bar{\lambda}^{-}_{\ell,t}=\bar{\lambda}_{\ell,t}-\bar{\gamma}_{\ell,t}$
for $(\ell,t)\in R$. Since $\bar{\gamma}\neq 0$ it follows that
$\bar{\lambda}^{+}\neq\bar{\lambda}^{-}$.

We now show that $\bar{\lambda}^{+},\bar{\lambda}^{-}$ are in the
$\bar{x}$-polytope. Let $\ell\in I,t\in I\cup\mathcal{C}$ such that
$\ell\notin\textsf{fit}(t)$. Therefore, $(\ell,t)\notin R$; thus,
$\bar{\lambda}^{+}_{\ell,t}=\bar{\lambda}_{\ell,t}=0$ because $\bar{\lambda}$
is in the $\bar{x}$-polytope. We conclude that (4) is satisfied for
$\bar{\lambda}^{+}$. Let $C\in\mathcal{C}$. Then,

$\sum_{\ell\in I}\bar{\lambda}^{+}_{\ell,C}\cdot s(\ell)=\sum_{\ell\in G\text{
s.t. }(\ell,t)\in R}(\bar{\phi}_{\ell,C}+\bar{\gamma}_{\ell,C})\cdot
s(\ell)+\sum_{\ell\in I\setminus G}\bar{\lambda}_{\ell,C}\cdot
s(\ell)\leq\left(1-s(C)\right)\cdot\bar{x}_{C}.$ (52)

The inequality is because $\bar{\phi}+\bar{\gamma}\in Q$. By (52) we conclude
that (5) is satisfied for $\bar{\lambda}^{+}$. Let $G^{\prime}\in\mathcal{G}$
and $C\in\mathcal{C}$. Then, if $G^{\prime}\neq G$ it holds that:

$\sum_{\ell\in G^{\prime}}\bar{\lambda}^{+}_{\ell,C}=\sum_{\ell\in
G}\bar{\lambda}_{\ell,C}\leq\bar{x}_{C}\cdot(k(G)-|G\cap C|)=L_{C,G}.$ (53)

The inequality is because $\bar{\lambda}$ is in the $\bar{x}$-polytope and
satisfies (6). Otherwise, $G^{\prime}=G$.

$\displaystyle\sum_{\ell\in G}\bar{\lambda}^{+}_{\ell,C}={}$
$\displaystyle\sum_{\ell\in G}\bar{\lambda}_{\ell,C}+\sum_{\ell\in
G}\bar{\gamma}_{\ell,C}=\sum_{\ell\in G}\bar{\lambda}_{\ell,C}+\sum_{\ell\in
G\text{ s.t. }(\ell,C)\in R}\bar{\gamma}_{\ell,C}$ (54) $\displaystyle\leq{}$
$\displaystyle\sum_{\ell\in
G}\bar{\lambda}_{\ell,C}+\left(L_{C,G}-\sum_{\ell\in
G}\bar{\lambda}_{\ell,C}\right)=L_{C,G}=\bar{x}_{C}\cdot(k(G)-|G\cap C|).$

The inequality is by (51). By (53) and (54) we conclude that (6) is satisfied
for $\bar{\lambda}^{+}$.

Let $j\in I$. We split into two cases.

  1. 1.

$j\notin G$. Then, by (2) and (4) for all $\ell\notin\textsf{group}(j)$ it
holds that $\bar{\lambda}^{+}_{\ell,j}=0$ and for all $\ell^{\prime}\in I$ it
holds that
$\bar{\lambda}^{+}_{\ell^{\prime},j}=\bar{\lambda}_{\ell^{\prime},j}$.
Therefore,

$\sum_{\ell\in
I}\bar{\lambda}^{+}_{\ell,j}=\sum_{\ell\in\textsf{group}(j)}\bar{\lambda}_{\ell,C}^{+}=\sum_{\ell\in\textsf{group}(j)}\bar{\lambda}_{\ell,C}\leq\sum_{C\in{\mathcal{C}}[j]}\bar{x}_{C}.$

  2. 2.

$j\in G$. Then, by (2) and (4) for all $\ell\notin G$ it holds that
$\bar{\lambda}^{+}_{\ell,j}=0$. Therefore,

$\displaystyle\sum_{\ell\in I}\bar{\lambda}^{+}_{\ell,j}={}$
$\displaystyle\sum_{\ell\in G}\bar{\lambda}^{+}_{\ell,j}=\sum_{\ell\in
G}\bar{\lambda}_{\ell,j}+\sum_{\ell\in G\text{ s.t. }(\ell,j)\in
R}\bar{\gamma}_{\ell,j}$ $\displaystyle\leq{}$ $\displaystyle\sum_{\ell\in
G}\bar{\lambda}_{\ell,j}+\left(L_{j,G}-\sum_{\ell\in
G}\bar{\lambda}_{\ell,j}\right)=L_{j,G}=\sum_{C\in{\mathcal{C}}[j]}\bar{x}_{C}.$

The inequality is by (51).

By the above, we conclude that (7) is satisfied for $\bar{\lambda}^{+}$.

Let $\ell\in I$. We split into two cases.

  1. 1.

$\ell\notin G$.

$\sum_{t\in I\cup{\mathcal{C}}}\bar{\lambda}^{+}_{\ell,t}=\sum_{t\in
I\cup{\mathcal{C}}}\bar{\lambda}_{\ell,t}\geq 1.$

The last inequality is because $\bar{\lambda}$ satisfies constraint (8) of the
$\bar{x}$-polytope.

  2. 2.

$\ell\in G$.

$\sum_{t\in I\cup{\mathcal{C}}}\bar{\lambda}^{+}_{\ell,t}\geq\sum_{t\in
T}\left(\bar{\lambda}_{\ell,t}+\bar{\gamma}_{\ell,t}\right)=\sum_{t\in
T}\bar{\lambda}_{\ell,t}+\sum_{t\in T\text{ s.t. }(\ell,t)\in
R}\bar{\gamma}_{\ell,t}=\sum_{t\in T}\bar{\lambda}_{\ell,t}\geq 1.$

The second equality is by (50).

By the above, constraint (8) is satisfied for $\bar{\lambda}^{+}$. Overall, we
conclude that $\bar{\lambda}^{+}$ is in the $\bar{x}$-polytope.

Using a symmetric argument it follows that $\bar{\lambda}^{-}$ is also in the
$\bar{x}$-polytope. Since
$\bar{\lambda}=\frac{\bar{\lambda}^{+}+\bar{\lambda}^{-}}{2}$, it follows that
$\bar{\lambda}$ is not a vertex of the $\bar{x}$-polytope. Contradiction.
Thus, $\bar{\phi}$ is a vertex of $Q$. ∎

Let $F=\\{\ell\in G~{}|~{}\exists t\in T\text{ s.t.
}\bar{\phi}_{\ell,t}\in(0,1)\\}$. By the definition of $\bar{\phi}$, it
suffices to show that $|F|\leq 2|T|$. For any $\ell\in I$ define
$\delta_{\ell}=|\\{t\in T~{}|~{}(\ell,t)\in R\\}|$ to be all of the
corresponding pairs of $\ell$ in $R$. It follows that $|R|=\sum_{\ell\in
I}\delta_{\ell}$. For $\ell\in F$, up to $\delta_{\ell}-1$ of the
corresponding inequalities of $\ell$ in (46) and (47) are tight: to satisfy
(47) for $\ell$ at least two inequalities corresponding to $\ell$ in (46) are
not tight. In addition, for $\ell\in G\setminus F$, up to $\delta_{\ell}$
corresponding constraints in (46) and (47) for $\ell$ are tight: to satisfy
(47) for $\ell$ at least one inequality corresponding to $\ell$ in (46) is not
tight. Moreover, there are at most $2|T|$ constraints in (48) and (49) that
can be tight. Hence, the number of tight constraints is at most

$\sum_{\ell\in F}(\delta_{\ell}-1)+\sum_{\ell\in G\setminus
F}\delta_{\ell}+2|T|\leq|R|-|F|+2|T|.$ (55)

As $\bar{\phi}$ is a vertex of $Q$, there are at least $|R|$ tight
inequalities. Thus, $|F|\leq 2|T|$. Note that for all $t\in
I\cup{\mathcal{C}}\setminus T$ and $\ell\in I$ it holds that
$\bar{\lambda}_{\ell,t}=0$ by the constraints of the $\bar{x}$-polytope; thus,
such entries cannot be fractional, and the number of fractional entries
corresponding to items in $G$ is at most $2|T|$. ∎

Proof of Lemma 3.4:

Note that for all $t\in I\cup{\mathcal{C}}\setminus T$ and $\ell\in I$ it
holds that $\bar{\lambda}_{\ell,t}=0$ by the constraints of the
$\bar{x}$-polytope; thus, such entries cannot be non-integral. In addition, by
Lemma B.3 and Lemma B.4 the number of non-integral entries is at most
$2|T|\cdot|T|$. Therefore,

$2|T|\cdot|T|\leq
2\left(|\textsf{supp}(\bar{x})|+k\cdot|\textsf{supp}(\bar{x})|\right)^{2}\leq
2\left(2k\cdot|\textsf{supp}(\bar{x})|\right)^{2}=8k^{2}|\textsf{supp}(\bar{x})|^{2}.$

The first inequality is because $|I\cap T|$ is upper bounded by the size of
$\textsf{supp}(\bar{x})$ times the number of items in each configuration in
$\textsf{supp}(\bar{x})$. ∎

##  Appendix C Omitted Proofs of Section 4

Proof of Lemma 4.1: Let $\ell_{1},\ldots,\ell_{r}$ be the items in $C\setminus
L$ in decreasing order such that for all $a,b\in[r],a<b$ it holds that
$\ell_{a}<\ell_{b}$. In addition, let
$U_{C}~{}=~{}\\{\ell_{1},\ldots,\ell_{h}\\}$ such that $h=\alpha$. For the
simplicity of the notations, for any $j\in[h]$ let $T_{j}=s\left(C\cap
L\cup\\{\ell_{1},\ldots,\ell_{j-1}\\}\right)$ be the total size of the large
items in $C$ and the first $j-1$ small items in $C$ according to the above
sorted order of items.888With a slight abuse of notation, assume that
$\\{\ell_{1},\ldots,\ell_{j-1}\\}=\emptyset$ for $j=1$. We use the following
auxiliary claims.

######  Claim C.1.

For all $i,k\in[h]$ which satisfy that $k>i+{\varepsilon}^{-4}$, it holds that
$s(\ell_{i})>\frac{s(\ell_{k})}{{\varepsilon}^{2}}$.

###### Proof.

Assume towards a contradiction that there are $i,k\in[h]$ which satisfy that
$k>i+{\varepsilon}^{-4}$ and
$s(\ell_{i})\leq\frac{s(\ell_{k})}{{\varepsilon}^{2}}$. Thus,

$s(\\{\ell_{i},\ell_{i+1},\ldots,\ell_{k}\\})\geq(k-i)\cdot
s(\ell_{k})\geq{\varepsilon}^{-4}\cdot
s(\ell_{k})\geq{\varepsilon}^{-4}\cdot{\varepsilon}^{2}\cdot
s(\ell_{i})={\varepsilon}^{-2}s(\ell_{i})$ (56)

The first inequality is because the items are in decreasing order that induces
a non increasing order of item sizes. The second inequality is because
$k>i+{\varepsilon}^{-4}$. The third inequality is by the assumption that
$s(\ell_{i})\leq\frac{s(\ell_{k})}{{\varepsilon}^{2}}$.

Note that it holds that $T_{i}<1$ since $T_{i}$ is the total size of items in
a proper subset of $C$ and the sizes of the items are strictly larger than
zero. Now, because $\ell_{i}\in U_{C}$ and $i<\alpha$, we conclude by (3) and
(9) that

$s(\ell_{i})>{\varepsilon}\left(1-T_{i}\right).$ (57)

Therefore,

$s(C)\geq T_{i}+s(\\{\ell_{i},\ldots,\ell_{k}\\})\geq
T_{i}+{\varepsilon}^{-1}\left(1-T_{i}\right)\geq
T_{i}+\left(1-T_{i}\right)+({\varepsilon}^{-1}-1)(1-T_{i})>1.$ (58)

The first inequality is because $C\cap L\cup\\{\ell_{1},\ldots,\ell_{i-1}\\}$
is disjoint to $\\{\ell_{i},\ldots,\ell_{k}\\}$. The second inequality is by
(56) and (57). The last inequality follows since $0<{\varepsilon}<0.1$ and
$0\leq T_{i}<1$. By (58), we reach a contradiction to the fact that $s(C)\leq
1$ because $C$ is a configuration. ∎

######  Claim C.2.

For any $i\in[h]$ such that $i+{\varepsilon}^{-4}<h-1$ it holds that
$\ell_{i}\in\mathcal{L}_{C}$.

###### Proof.

$s(\ell_{i})>\frac{s(\ell_{h-1})}{{\varepsilon}^{2}}>{\varepsilon}^{-2}\cdot{\varepsilon}(1-T_{h-1})={\varepsilon}^{-1}(1-T_{h-1})\geq{\varepsilon}^{-1}(1-s(R(C))).$
(59)

The first inequality is by Claim C.1. The second inequality is because
$h-1<h\leq\alpha$; thus, similarly to (57), it holds that
$s(\ell_{h-1})>{\varepsilon}\left(1-T_{h-1}\right)$. The last inequality is
because $T_{h-1}$ is the total size in a proper subset of $R(C)$; thus,
$T_{h-1}\leq s(R(C))$. By (59), we conclude that for any $i\in[h]$ such that
$i+{\varepsilon}^{-4}<h-1$ it holds that $\ell_{i}\in\mathcal{L}_{C}$. ∎

Now, using the above claim:

$|\mathcal{L}_{C}|\geq
h-2-{\varepsilon}^{-4}\geq{\varepsilon}^{-5}-2{\varepsilon}^{-4}={\varepsilon}^{-4}({\varepsilon}^{-1}-2)>{\varepsilon}^{-4}.$

The first inequality is since by Claim C.2 it holds that
$\ell_{1},\ldots,\ell_{t}\in\mathcal{L}_{C}$ for $t=h-2-{\varepsilon}^{-4}$.
The second inequality is because $h=\alpha$. ∎

Proof of Lemma 4.2: Let $C\in\mathcal{C}$. We split the proof into the
following claims which together form the proof of the lemma.

######  Claim C.3.

Condition 1 of Lemma 4.2 holds for $|U_{C}|=\alpha$.

###### Proof.

$\|\bar{w}^{C}\|=\sum_{\ell\in\mathcal{L}_{C}}\bar{w}^{C}_{R(C)\setminus\\{\ell\\}}=\sum_{\ell\in\mathcal{L}_{C}}\frac{1}{|\mathcal{L}_{C}|-1}=\frac{|\mathcal{L}_{C}|}{|\mathcal{L}_{C}|-1}\leq\frac{{\varepsilon}^{-4}}{{\varepsilon}^{-4}-1}\leq
1+2{\varepsilon}^{4}.$

The first equality is because by the definition $\bar{w}^{C}$, for any other
entry $C^{\prime}$ that is not in the second summation it holds that
$\bar{w}^{C}_{C^{\prime}}=0$. The second equality is by the definition of
$\bar{w}^{C}$ in case that $|U_{C}|=\alpha$. The first inequality is because
$|U_{C}|=\alpha$; therefore, by Lemma 4.1 it holds that
$|\mathcal{L}_{C}|\geq{\varepsilon}^{-4}$. The last inequality is because
$0<{\varepsilon}<0.1$. ∎

######  Claim C.4.

Condition 2 of Lemma 4.2 holds for $|U_{C}|=\alpha$.

###### Proof.

Let $\ell\in R(C)$. Then,

$\sum_{C^{\prime}\in\mathcal{C}[\ell]}\bar{w}^{C}_{C^{\prime}}\geq\sum_{j\in\mathcal{L}_{C}\setminus\\{\ell\\}}\bar{w}^{C}_{R(C)\setminus\\{j\\}}=\sum_{j\in\mathcal{L}_{C}\setminus\\{\ell\\}}\frac{1}{|\mathcal{L}_{C}|-1}\geq\frac{|\mathcal{L}_{C}|-1}{|\mathcal{L}_{C}|-1}=1.$

The first inequality is since for any $j\in\mathcal{L}_{C}\setminus\\{\ell\\}$
it holds that $R(C)\setminus\\{j\\}\in\mathcal{C}[\ell]$ and that all entries
in $\bar{w}^{C}$ are non-negative. The first equality is by the definition of
$\bar{w}^{C}$ in case that $|U_{C}|=\alpha$. The last inequality is because
$|\mathcal{L}_{C}\setminus\\{\ell\\}|\geq|\mathcal{L}_{C}|-1$. ∎

######  Claim C.5.

Condition 3 of Lemma 4.2 holds for $|U_{C}|=\alpha$.

###### Proof.

For the third condition of the lemma, let
$C^{\prime}\in\textsf{supp}(\bar{w}^{C})$. By the definition of $\bar{w}^{C}$
in case that $|U_{C}|=\alpha$, there is $\ell\in\mathcal{L}_{C}$ such that
$C^{\prime}=R(C)\setminus\\{\ell\\}$. Now,

$1-s(R(C))=1-s(R(C)\setminus\\{\ell\\})-s(\ell)\leq
1-s(R(C)\setminus\\{\ell\\})-\frac{1-s(R(C))}{{\varepsilon}}.$ (60)

The first equality is because $\ell\in\mathcal{L}_{C}$ and
$\mathcal{L}_{C}\subseteq R(C)$. The first inequality is by the definition of
$\mathcal{L}_{C}$. Therefore,

$1-s(R(C))\leq\left(\frac{1}{1+\frac{1}{{\varepsilon}}}\right)(1-s(R(C)\setminus\\{\ell\\}))\leq{\varepsilon}(1-s(R(C)\setminus\\{\ell\\})).$
(61)

The first inequality is by (60). Let $j\in C\setminus R(C)$. Now,

$s(j)\leq 1-s(R(C))\leq{\varepsilon}(1-s(R(C)\setminus\\{\ell\\})).$ (62)

The first inequality is because $j\notin R(C)$ and $s(C)\leq 1$. The second
inequality is by (61). Therefore, by (62) we get that
$j\in\textsf{fit}(C^{\prime})$ by (3) (because $j\in C\setminus R(C)$ it holds
that $j\notin L$). Because there are no restrictions over $j$ besides that
$j\in C\setminus R(C)$, we conclude that $C\setminus
R(C)\subseteq\textsf{fit}(C^{\prime})$. In addition,

$s(C\setminus R(C))\leq 1-s(R(C))\leq
1-s(R(C)\setminus\\{\ell\\})=1-s(C^{\prime}).$

The first inequality is because $R(C)\subseteq C$ and $s(C)\leq 1$. The second
inequality is because $s(\ell)\geq 0$. The first equality is by the definition
of $C^{\prime}$. ∎

######  Claim C.6.

Condition 4 of Lemma 4.2 holds.

###### Proof.

let $C^{\prime}\in\textsf{supp}(\bar{w}^{C})$. Assume towards a contradiction
that $s(C^{\prime}\setminus L)>{\varepsilon}$. Therefore,

${\varepsilon}<s(C^{\prime}\setminus L)\leq 1-s(C^{\prime}\cap L).$ (63)

The second inequality is because $C^{\prime}\in{\mathcal{C}}$ is a
configuration. Recall $\ell_{1}$ from (9) for $C^{\prime}$; it also holds that

$s(\ell_{1})\leq{\varepsilon}^{2}={\varepsilon}\cdot{\varepsilon}<{\varepsilon}\cdot\left(1-s(C^{\prime}\cap
L)\right).$ (64)

The first inequality is because $\ell_{1}\in I\setminus L$. The last
inequality is by (63). Therefore, by (64) we get that
$\ell_{1}\in\textsf{fit}(C^{\prime}\cap L)$ by (3). By the definition of the
relaxation $\bar{w}^{C}$ it holds that $C^{\prime}\cap L=C\cap L$, thus
$\ell_{1}\in\textsf{fit}(C\cap L)$. Then, by (9) and the definition of $U_{C}$
we conclude that $U_{C}=\emptyset$. Hence, by the definition of $\bar{w}^{C}$
and that $C^{\prime}\in\textsf{supp}(\bar{w}^{C})$, it holds that
$C^{\prime}=C\cap L$; thus, $s(C^{\prime}\setminus L)=0$. For any
${\varepsilon}>0$, this is a contradiction that $s(C^{\prime}\setminus
L)>{\varepsilon}$. ∎

######  Claim C.7.

Condition 5 of Lemma 4.2 holds.

###### Proof.

Let $C^{\prime}\in\textsf{supp}(\bar{w}^{C})$ and $G\in{\mathcal{G}}$. Now,

$\left|G\cap\left(C\setminus R(C)\right)\right|\leq|G\cap C|-|G\cap R(C)|\leq
k(G)-|G\cap R(C)|\leq k(G)-|G\cap C^{\prime}|.$

The last inequality is because by the definition of $\bar{w}^{C}$ it holds
that $C^{\prime}\subseteq R(C)$ ∎

######  Claim C.8.

Conditions 1-3 of Lemma 4.2 hold for $|U_{C}|<\alpha$.

###### Proof.

For the first condition of the lemma:

$\|\bar{w}^{C}\|=\bar{w}^{C}_{R(C)}=1\leq 1+2{\varepsilon}^{4}.$

The first equality is because by the definition $\bar{w}^{C}$, for any other
configuration $C^{\prime}\in\mathcal{C}\setminus\\{R(C)\\}$ it holds that
$\bar{w}^{C}_{C^{\prime}}=0$. The second equality is by the definition of
$\bar{w}^{C}$ in case that $|U_{C}|<\alpha$.

For the second condition of the lemma, let $\ell\in R(C)$. Then,

$\sum_{C^{\prime}\in\mathcal{C}[\ell]}\bar{w}^{C}_{C^{\prime}}=\bar{w}^{C}_{R(C)}=1.$

The first equality is because by the definition $\bar{w}^{C}$, for any other
configuration $C^{\prime}\in\mathcal{C}\setminus\\{R(C)\\}$ it holds that
$\bar{w}^{C}_{C^{\prime}}=0$. The second equality is bythe definition of
$\bar{w}^{C}$ in case that $|U_{C}|<\alpha$.

For the third condition of the lemma, let
$C^{\prime}\in\textsf{supp}(\bar{w}^{C})$. By the definition of $\bar{w}^{C}$
in case that $|U_{C}|<\alpha$, it holds that $C^{\prime}=R(C)$. Let $j\in
C\setminus R(C)$. It holds that $j\in\textsf{fit}(C^{\prime})$ by (9), since
$|U_{C}|<\alpha$. Because there are no restrictions over $j$ besides that
$j\in C\setminus R(C)$, we conclude that $C\setminus
R(C)\subseteq\textsf{fit}(C^{\prime})$. In addition,

$s(C\setminus R(C))\leq 1-s(R(C))=1-s(C^{\prime}).$

The first inequality is because $R(C)\subseteq C$ and $s(C)\leq 1$. The first
equality is by the definition of $C^{\prime}$. ∎

The proof of Lemma 4.2 follows by Claim C.3, Claim C.4, Claim C.5, Claim C.6,
Claim C.8, and Claim C.7.

Proof of Lemma 3.6: We use in the proof of Lemma 3.6 the following claims.

######  Claim C.9.

Algorithm 2 is polynomial.

###### Proof.

The number of elements over which the loop in Step 2 iterates is polynomial,
since $|\textsf{supp}(\bar{x})|$ is at most the encoding size of the input (in
a sparse representation). Let $C\in\textsf{supp}(\bar{x})$ be a configuration
in the support of $\bar{x}$. It follows by (9) that $U_{C}$ can be easily
computed in polynomial time by iteratively adding items from $C\setminus L$ in
decreasing order of the items. Therefore, given $U_{C}$, the relaxation of $C$
that is $\bar{w}^{C}$ can be computed in polynomial time: by the definition of
$\bar{w}^{C}$, the number of nonzero entries in $\bar{w}^{C}$ is at most
$|\mathcal{L}_{C}|$, which is polynomial in the size of the instance. This is
since $\mathcal{L}_{C}\subseteq I$ is a subset of the items. Finally, Step 2
is also polynomial as $\bar{y}$ is a linear combination of a polynomial number
(i.e., $|\textsf{supp}(\bar{x})|$) of vectors, each with a polynomial number
of nonzero entries. By the above, the claim follows. ∎

######  Claim C.10.

For any $0<{\varepsilon}<0.1$, an ${\varepsilon}$-structured BPP instance
$\mathcal{I}$, and a solution $\bar{x}$ to the configuration LP in (1),
Algorithm 2 returns a prototype $\bar{y}$ of $\mathcal{I}$ with
$\bar{\lambda}$ in the $\bar{y}$-polytope such that for all $\ell,j\in
I,\ell\neq j$ it holds that $\bar{\lambda}_{\ell,j}=0$.

###### Proof.

We define below a point
$\bar{\lambda}\in\mathbb{R}^{I\times(I\cup\mathcal{C})}_{\geq 0}$ in the
$\bar{y}$-polytope. Thus, it follows that the $\bar{y}$-polytope is non-empty.
For any $C\in\mathcal{C}$, define the point of $C$ as a vector
$\bar{\gamma}^{C}\in\mathbb{R}^{I\times(I\cup\mathcal{C})}_{\geq 0}$ as
follows. For any $\ell\in R(C)$, define

$\bar{\gamma}^{C}_{\ell,\ell}=1.$ (65)

Moreover, for any $\ell\in C\setminus R(C)$ and $C^{\prime}\in\mathcal{C}$
define

$\bar{\gamma}^{C}_{\ell,C^{\prime}}=\bar{w}^{C}_{C^{\prime}}.$ (66)

For any other $\ell\in I$ and $t\in(I\cup\mathcal{C})$ define

$\bar{\gamma}^{C}_{\ell,t}=0.$ (67)

Finally, define

$\bar{\lambda}=\sum_{C\in\mathcal{C}}\bar{x}_{C}\cdot\bar{\gamma}^{C}.$ (68)

We show below that all constraints of the $\bar{y}$-polytope are satisfied for
$\bar{\lambda}$. Let $\ell\in I$ and $t\in I\cup\mathcal{C}$ such that
$\ell\notin\textsf{fit}\left(t\right)$. Then,

$\bar{\lambda}_{\ell,t}=\sum_{C\in\mathcal{C}}\bar{y}_{C}\cdot\bar{\gamma}^{C}_{\ell,t}=\sum_{C\in\mathcal{C}}\bar{y}_{C}\cdot
0=0.$ (69)

The first equality is by (68). Because $\ell\notin\textsf{fit}\left(t\right)$,
then $\ell\neq t$ by (2); moreover, for all $C\in\mathcal{C}$ such that
$\ell\in C\setminus R(C)$ and $C^{\prime}\in\textsf{supp}(\bar{w}^{C})$, it
holds that $t\neq C^{\prime}$ because $\ell\in\textsf{fit}(C^{\prime})$ by
Lemma 4.2. Therefore, by (67) the second equality follows. By (69) we conclude
that constraint (4) is satisfied for $\bar{\lambda}$.

Let $C\in\mathcal{C}$. Then,

$\displaystyle\sum_{\ell\in I}\bar{\lambda}_{\ell,C}\cdot s(\ell)$
$\displaystyle=\sum_{\ell\in
I~{}}\sum_{C^{\prime}\in\mathcal{C}}\bar{x}_{C^{\prime}}\cdot\bar{\gamma}^{C^{\prime}}_{\ell,C}\cdot
s(\ell)=\sum_{C^{\prime}\in\mathcal{C}~{}}\sum_{\ell\in
I}\bar{x}_{C^{\prime}}\cdot\bar{\gamma}^{C^{\prime}}_{\ell,C}\cdot s(\ell)$
(70) $\displaystyle={}$
$\displaystyle\sum_{C^{\prime}\in\mathcal{C}~{}}\sum_{\ell\in
C^{\prime}\setminus
R(C^{\prime})}\bar{x}_{C^{\prime}}\cdot\bar{w}^{C^{\prime}}_{C}\cdot
s(\ell)=\sum_{C^{\prime}\in\mathcal{C}}\bar{x}_{C^{\prime}}\cdot\bar{w}^{C^{\prime}}_{C}\cdot
s\left(C^{\prime}\setminus R(C^{\prime})\right)$ $\displaystyle\leq{}$
$\displaystyle\sum_{C^{\prime}\in\mathcal{C}}\bar{x}_{C^{\prime}}\cdot\bar{w}^{C^{\prime}}_{C}\cdot\left(1-s(C)\right)=(1-s(C))\cdot\sum_{C^{\prime}\in\textsf{supp}(\bar{x})}\bar{x}_{C^{\prime}}\cdot\bar{w}^{C^{\prime}}_{C}=(1-s(C))\bar{y}_{C}.$

The first equality is by (68). The second equality is by changing the order of
summation. The third equality is by (65), (66) and (67). The inequality is
because for all $C^{\prime}\in\mathcal{C}$, if
$C\in\textsf{supp}({\bar{w}^{C^{\prime}}})$ then $s(C^{\prime}\setminus
R(C^{\prime}))\leq 1-s(C)$ by Lemma 4.2. The last equality is by Step 2 of
Algorithm 2. Therefore, by (70) we conclude that constraint (5) is satisfied
for $\bar{\lambda}$.

Let $G\in\mathcal{G}$ and $C\in\mathcal{C}$. Then,

$\displaystyle\sum_{\ell\in G}\bar{\lambda}_{\ell,C}={}$
$\displaystyle\sum_{\ell\in
G~{}}\sum_{C^{\prime}\in\mathcal{C}}\bar{x}_{C^{\prime}}\cdot\bar{\gamma}^{C^{\prime}}_{\ell,C}=\sum_{C^{\prime}\in\mathcal{C}~{}}\sum_{\ell\in
G}\bar{x}_{C^{\prime}}\cdot\bar{\gamma}^{C^{\prime}}_{\ell,C}=\sum_{C^{\prime}\in\mathcal{C}~{}~{}}\sum_{\ell\in
G\cap\left(C^{\prime}\setminus
R(C^{\prime})\right)}\bar{x}_{C^{\prime}}\cdot\bar{w}^{C^{\prime}}_{C}$ (71)
$\displaystyle={}$ $\displaystyle\sum_{C^{\prime}\in\mathcal{C}\text{ s.t.
}C\in\textsf{supp}(\bar{w}^{C^{\prime}})~{}~{}}\bar{x}_{C^{\prime}}\cdot\bar{w}^{C^{\prime}}_{C}\sum_{\ell\in
G\cap\left(C^{\prime}\setminus
R(C^{\prime})\right)}1\leq\sum_{C^{\prime}\in\mathcal{C}}\bar{x}_{C^{\prime}}\cdot\bar{w}^{C^{\prime}}_{C}\cdot\left(k(G)-|G\cap
C|\right)$ $\displaystyle={}$ $\displaystyle\left(k(G)-|G\cap
C|\right)\sum_{C^{\prime}\in\textsf{supp}(\bar{x})~{}}\bar{x}_{C^{\prime}}\cdot\bar{w}^{C^{\prime}}_{C}=\bar{y}_{C}\cdot\left(k(G)-|G\cap
C|\right)$

The first equality is by (68). The second equality is by changing the order of
summation. The third equality is by (65), (66) and (67). The inequality is by
Condition 5 of Lemma 4.2. The last equality is by Step 2 of Algorithm 2.
Therefore, by (71) we conclude that constraint (6) is satisfied for
$\bar{\lambda}$.

Let $j\in I$. Then,

$\displaystyle\sum_{\ell\in I}\bar{\lambda}_{\ell,j}={}$
$\displaystyle\sum_{\ell\in
I~{}}\sum_{C\in\mathcal{C}}\bar{x}_{C}\cdot\bar{\gamma}^{C}_{\ell,j}=\sum_{C\in\mathcal{C}~{}}\sum_{\ell\in
I}\bar{x}_{C}\cdot\bar{\gamma}^{C}_{\ell,j}=\sum_{C\in\mathcal{C}[j]\text{
s.t. }j\in R(C)}\bar{x}_{C}$ (72) $\displaystyle\leq{}$
$\displaystyle\sum_{C\in\mathcal{C}[j]\text{ s.t. }j\in
R(C)}\bar{x}_{C}\cdot\left(\sum_{C^{\prime}\in\mathcal{C}[j]}\bar{w}^{C}_{C^{\prime}}\right)\leq\sum_{C\in\mathcal{C}[j]}\sum_{C^{\prime}\in\mathcal{C}[j]}\bar{x}_{C}\cdot\bar{w}^{C}_{C^{\prime}}$
$\displaystyle={}$
$\displaystyle\sum_{C^{\prime}\in\mathcal{C}[j]}\sum_{C\in\mathcal{C}[j]}\bar{x}_{C}\cdot\bar{w}^{C}_{C^{\prime}}\leq\sum_{C^{\prime}\in\mathcal{C}[j]}\sum_{C\in\textsf{supp}(\bar{x})}\bar{x}_{C}\cdot\bar{w}^{C}_{C^{\prime}}=\sum_{\begin{subarray}{c}C^{\prime}\in\mathcal{C}[j]\end{subarray}}\bar{y}_{C^{\prime}}=\sum_{\begin{subarray}{c}C\in\mathcal{C}[j]\end{subarray}}\bar{y}_{C}.$

The first equality is by (68). The second equality is by changing the order of
summation. The third equality is by (65), (66) and (67). The first inequality
is because for all $C\in{\mathcal{C}}$ and $j\in R(C)$ it holds that
$\sum_{C^{\prime}\in\mathcal{C}[j]}\bar{w}^{C}_{C^{\prime}}\geq 1$ by Lemma
4.2. The second inequality is because for all $C,C^{\prime}\in{\mathcal{C}}$
it holds that $\bar{x}_{C}\cdot\bar{w}^{C}_{C^{\prime}}\geq 0$. The fourth
equality is is by changing the order of summation. The third inequality is
because for all $C\in\mathcal{C}[j]\setminus\textsf{supp}(\bar{x})$ it holds
that $\bar{x}_{C}\cdot\bar{w}^{C}_{C^{\prime}}=0$. The fifth equality is by
Step 2 of Algorithm 2. The sixth equality is by a change in the notation of a
variable. Therefore, by (72) we conclude that constraint (7) is satisfied for
$\bar{\lambda}$.

Let $\ell\in I$. Then, we use the following equations.

$\sum_{t\in I}\bar{\lambda}_{\ell,t}=\sum_{t\in
I~{}}\sum_{C\in\mathcal{C}}\bar{x}_{C}\cdot\bar{\gamma}^{C}_{\ell,t}=\sum_{C\in\mathcal{C}~{}}\sum_{t\in
I}\bar{x}_{C}\cdot\bar{\gamma}^{C}_{\ell,t}=\sum_{C\in\mathcal{C}[\ell]\text{
s.t. }\ell\in R(C)}\bar{x}_{C}.$ (73)

The first equality is by (68). The second equality is by changing the order of
summation. The third equality is by (65) and (67). In addition,

$\displaystyle\sum_{t\in\mathcal{C}}\bar{\lambda}_{\ell,t}={}$
$\displaystyle\sum_{t\in\mathcal{C}~{}}\sum_{C\in\mathcal{C}}\bar{x}_{C}\cdot\bar{\gamma}^{C}_{\ell,t}=\sum_{C\in\mathcal{C}~{}}\sum_{t\in\mathcal{C}}\bar{x}_{C}\cdot\bar{\gamma}^{C}_{\ell,t}=\sum_{C\in\mathcal{C}[\ell]\text{
s.t. }\ell\in C\setminus
R(C)~{}}\sum_{t\in\mathcal{C}}\bar{x}_{C}\cdot\bar{w}^{C}_{t}$ (74)
$\displaystyle={}$ $\displaystyle\sum_{C\in\mathcal{C}[\ell]\text{ s.t.
}\ell\in C\setminus
R(C)~{}}\bar{x}_{C}\sum_{t\in\mathcal{C}}\bar{w}^{C}_{t}\geq\sum_{C\in\mathcal{C}[\ell]\text{
s.t. }\ell\in C\setminus
R(C)~{}}\bar{x}_{C}\sum_{t\in\mathcal{C}[\ell]}\bar{w}^{C}_{t}\geq\sum_{C\in\mathcal{C}[\ell]\text{
s.t. }\ell\in C\setminus R(C)~{}}\bar{x}_{C}.$

The first equality is by (68). The second equality is by changing the order of
summation. The third equality is by (66) and (67). The first inequality is
because $\mathcal{C}[\ell]\subseteq\mathcal{C}$. The second inequality is
because $\sum_{t\in\mathcal{C}[\ell]}\bar{w}^{C}_{t}\geq 1$ by Lemma 4.2.
Thus,

$\sum_{t\in I\cup\mathcal{C}}\bar{\lambda}_{\ell,t}=\sum_{t\in
I}\bar{\lambda}_{\ell,t}+\sum_{t\in\mathcal{C}}\bar{\lambda}_{\ell,t}\geq\sum_{C\in\mathcal{C}[\ell]\text{
s.t. }\ell\in R(C)}\bar{x}_{C}+\sum_{C\in\mathcal{C}[\ell]\text{ s.t. }\ell\in
C\setminus R(C)~{}}\bar{x}_{C}=\sum_{C\in\mathcal{C}[\ell]}\bar{x}_{C}\geq 1.$
(75)

The first equality is because $I\cap\mathcal{C}=\emptyset$. The first
inequality is by (73) and (1). The second equality is because for all
$C\in\mathcal{C}[\ell]$ either $\ell\in R(C)$ or $\ell\in C\setminus R(C)$.
The last inequality is because $\bar{x}$ is a solution for (1). Therefore, by
(75), constraint (8) is satisfied for $\bar{\lambda}$. In summary, we conclude
that $\bar{\lambda}$ is a point in the $\bar{y}$-polytope; hence, the
$\bar{y}$-polytope is non-empty.

∎

######  Claim C.11.

For any $0<{\varepsilon}<0.1$, an ${\varepsilon}$-structured BPP instance
$\mathcal{I}$, and a prototype $\bar{x}$ of $\mathcal{I}$, Algorithm 2 returns
a prototype $\bar{y}$ such that $||\bar{y}||\leq(1+{\varepsilon})||\bar{x}||$.

###### Proof.

$\displaystyle\|\bar{y}\|={}$
$\displaystyle\left\|\sum_{C\in\textsf{supp}(\bar{x})}\bar{x}_{C}\cdot\bar{w}^{C}\right\|\leq\sum_{C\in\textsf{supp}(\bar{x})}\bar{x}_{C}\cdot\|\bar{w}^{C}\|\leq\sum_{C\in\textsf{supp}(\bar{x})}\bar{x}_{C}\cdot(1+2{\varepsilon}^{4})=(1+2{\varepsilon}^{4})\|\bar{x}\|\leq(1+{\varepsilon})\|\bar{x}\|.$

The first equality is by Step 2 of Algorithm 2. The first inequality is by the
triangle inequality. The second inequality is because
$\|\bar{w}^{C}\|\leq(1+2{\varepsilon}^{4})$ by Lemma 4.2 for all
$C\in\textsf{supp}(\bar{x})$. The last inequality is because
$0<{\varepsilon}<0.1$.

∎

######  Claim C.12.

For any $0<{\varepsilon}<0.1$, an ${\varepsilon}$-structured BPP instance
$\mathcal{I}$, and a prototype $\bar{x}$ of $\mathcal{I}$, Algorithm 2 returns
a prototype $\bar{y}$ such that for all $C\in\textsf{supp}(y)$ it holds that
$|C|\leq{\varepsilon}^{-10}$.

###### Proof.

Let $C\in\textsf{supp}(\bar{y})$ be a configuration. Because
$C\in\textsf{supp}(\bar{y})$, then by Step 2 of Algorithm 2, there is
$C^{\prime}\in\textsf{supp}(\bar{x})$ such that $\bar{w}^{C^{\prime}}_{C}\neq
0$. Therefore,

$|C|\leq|R(C^{\prime})|=|C^{\prime}\cap L\cup
U_{C^{\prime}}|\leq|C^{\prime}\cap
L|+|U_{C^{\prime}}|\leq{\varepsilon}^{-2}+\alpha\leq
2{\varepsilon}^{-6}\leq{\varepsilon}^{-10}.$

The first inequality is because the maximal number of items in $C$ is bounded
by $|R(C^{\prime})|$ by the definition of the relaxation vector of a
configuration. The first equality is by the definition of $R(C^{\prime})$. The
second inequality is by the union bound. The third inequality is since the
size of each large item in $L$ is at least ${\varepsilon}^{2}$ and there can
be at most ${\varepsilon}^{-2}$ such items in a configuration without
exceeding the maximal total size of items in a configuration which is $1$;
moreover, by (9) it holds that $|U_{C}|\leq\alpha$. The fourth inequality is
because $\alpha=\lceil{\varepsilon}^{-5}\rceil$. The last inequality is
because $0<{\varepsilon}<0.1$. ∎

######  Claim C.13.

For any $0<{\varepsilon}<0.1$, an ${\varepsilon}$-structured BPP instance
$\mathcal{I}$, and a prototype $\bar{x}$ of $\mathcal{I}$, Algorithm 2 returns
a prototype $\bar{y}$ such that for all $C\in\textsf{supp}(y)$ it holds that
$s(C\setminus L)\leq{\varepsilon}$.

###### Proof.

Let $C\in\textsf{supp}(\bar{y})$ be a configuration. Because
$C\in\textsf{supp}(\bar{y})$, then by Step 2 of Algorithm 2, there is
$C^{\prime}\in\textsf{supp}(\bar{x})$ such that $\bar{w}^{C^{\prime}}_{C}\neq
0$. Therefore, $C\in\textsf{supp}(\bar{w}^{C^{\prime}})$ and it follows that
$s(C\setminus L)\leq{\varepsilon}$ by Lemma 4.2. ∎

######  Claim C.14.

for every $\ell\in I$ it holds that
$\sum_{C\in{\mathcal{C}}[\ell]}{\bar{y}}_{C}\leq 2$.

###### Proof.

$\displaystyle\sum_{C\in{\mathcal{C}}[\ell]}{\bar{y}}_{C}={}$
$\displaystyle\sum_{C\in{\mathcal{C}}[\ell]~{}}\sum_{C^{\prime}\in\textsf{supp}(\bar{x})}\bar{x}_{C^{\prime}}\cdot\bar{w}^{C^{\prime}}_{C}=\sum_{C^{\prime}\in\textsf{supp}(\bar{x})~{}}\sum_{C\in{\mathcal{C}}[\ell]}\bar{x}_{C^{\prime}}\cdot\bar{w}^{C^{\prime}}_{C}\leq\sum_{C^{\prime}\in\textsf{supp}(\bar{x})~{}}\bar{x}_{C^{\prime}}\cdot\sum_{C\in{\mathcal{C}}}\bar{w}^{C^{\prime}}_{C}$
$\displaystyle={}$
$\displaystyle\sum_{C^{\prime}\in\textsf{supp}(\bar{x})~{}}\bar{x}_{C^{\prime}}\cdot\|\bar{w}^{C^{\prime}}\|\leq\sum_{C^{\prime}\in\textsf{supp}(\bar{x})~{}}\bar{x}_{C^{\prime}}\cdot(1+2{\varepsilon}^{4})\leq\sum_{C^{\prime}\in\textsf{supp}(\bar{x})~{}}\bar{x}_{C^{\prime}}\cdot
2=2\cdot\|\bar{x}\|=2.$

The first equality is by Step 2 of Algorithm 2. The second inequality is
because $\|\bar{w}^{C^{\prime}}\|\leq(1+2{\varepsilon}^{4})$ by Lemma 4.2. The
third inequality is because $0<{\varepsilon}<0.1$. The last equality is by
(1). ∎

The proof of Lemma 3.6 follows by Claim C.9, Claim C.10, Claim C.11, Claim
C.12, Claim C.13, and Claim C.14. ∎

##  Appendix D Omitted Proofs of Section 5

Proof of Lemma 5.1: We prove the two properties of the lemma below.

  1. 1.

$\displaystyle\sum_{\ell\in I\setminus L~{}}f_{\bar{y}}(\ell)\cdot s(\ell)={}$
$\displaystyle\sum_{\ell\in I\setminus
L~{}}\sum_{C\in\mathcal{C}[\ell]}\bar{y}_{C}\cdot
s(\ell)=\sum_{C\in\mathcal{C}~{}}\sum_{\ell\in C\setminus L}\bar{y}_{C}\cdot
s(\ell)=\sum_{C\in\mathcal{C}}\bar{y}_{C}\sum_{\ell\in C\setminus L}s(\ell)$
$\displaystyle={}$ $\displaystyle\sum_{C\in\mathcal{C}}\bar{y}_{C}\cdot
s(C\setminus
L)\leq\sum_{C\in\mathcal{C}}\bar{y}_{C}\cdot{\varepsilon}={\varepsilon}\sum_{C\in\mathcal{C}}\bar{y}_{C}={\varepsilon}\|\bar{y}\|.$

The first equality is by the definition of frequency. The second equality is
by changing the order of summation. The inequality follows since $\bar{y}$
holds the conditions of Lemma 3.7.

  2. 2.

Assume towards a contradiction that there is
$G\in\mathcal{G}\setminus\mathcal{G}_{\eta}$ such that $f_{\bar{y}}(G\setminus
L)>{\varepsilon}\cdot\|\bar{y}\|$. Therefore, by the definition of
${\mathcal{G}}_{\eta}$ as the set of groups with maximal frequncies of small
items, it holds that

$f_{\bar{y}}(G_{\eta}\setminus L)>{\varepsilon}\cdot\|\bar{y}\|.$ (76)

We reach a contradiction by the following.

$\sum_{\ell\in I}f_{\bar{y}}(\ell)=\sum_{\ell\in
I~{}}\sum_{C\in\mathcal{C}[\ell]}\bar{y}_{C}=\sum_{C\in\mathcal{C}~{}}\sum_{\ell\in
C}\bar{y}_{C}\leq\sum_{C\in\mathcal{C}~{}}{\varepsilon}^{-10}\cdot\bar{y}_{C}={\varepsilon}^{-10}\|\bar{y}\|.$
(77)

The first equality is by the definition of the frequency. The second equality
is by changing the order of summation. The inequality follows since $\bar{y}$
holds the conditions of Lemma 3.7; thus, for all $C\in\textsf{supp}(\bar{y})$
it holds that $|C|\leq{\varepsilon}^{-10}$. In addition,

$\sum_{\ell\in I}f_{\bar{y}}(\ell)\geq\sum_{i\in[\eta]~{}}\sum_{\ell\in
G_{i}\setminus L}f_{\bar{y}}(\ell)\geq\eta\cdot f_{\bar{y}}(G_{\eta}\setminus
L)>\eta\cdot{\varepsilon}\cdot\|\bar{y}\|>{\varepsilon}^{-10}\|\bar{y}\|.$
(78)

The first inequality is because for all $\ell\in I$ it holds that
$f_{\bar{y}}(\ell)\geq 0$. The second inequality is because for all
$G^{\prime}\in{\mathcal{G}}_{\eta}$ it holds that
$f_{\bar{y}}(G^{\prime}\setminus L)\geq f_{\bar{y}}(G_{\eta}\setminus L)$. The
third inequality is by (76). The last inequality is since
$\eta={\varepsilon}^{-12}$ or ${\mathcal{G}}_{\eta}={\mathcal{G}}$. By (77)
and (78) we reach a contradiction. ∎

We use the following auxiliary claim.

######  Claim D.1.

$|{\mathcal{A}}\cup{\mathcal{G}}_{\eta}|\leq 2K({\varepsilon})$.

###### Proof.

$|{\mathcal{A}}\cup{\mathcal{G}}_{\eta}|\leq|{\mathcal{A}}|+|{\mathcal{G}}_{\eta}|\leq
K({\varepsilon})+\eta\leq 2K({\varepsilon}).$

The second inequality is because $\mathcal{I}$ is ${\varepsilon}$-structured,
there can be at most $K({\varepsilon})$ massive groups by (10) and Definition
2.1. The third inequality is because
$K({\varepsilon})={\varepsilon}^{-{\varepsilon}^{-2}}$,
$\eta\leq{\varepsilon}^{-12}$, and ${\varepsilon}<0.1$. ∎

Proof of Lemma 5.3: Let $C\in\textsf{supp}(\bar{y})$. We show the properties
of the lemma below.

  1. 1.

$\displaystyle
s\left(P(C)\right)\leq\sum_{\Phi\in\mathcal{Q}}s\left(\textsf{last}_{|C\cap\Phi|}(\Phi)\right)\leq{}$
$\displaystyle\sum_{\Phi\in\mathcal{Q}}s\left(C\cap\Phi\right)\leq s(C).$ (79)

The second inequality is because for all $\Phi\in\mathcal{Q}$ it holds that
$\textsf{last}_{|C\cap\Phi|}(\Phi)$ contains the $|C\cap\Phi|$ items in $\Phi$
with minimal size. The last inequality is because each item belongs to at most
one class in $\mathcal{Q}$.

  2. 2.

Let $\ell\in\textsf{fit}(C)$. First, by (3) it holds that
$s(\ell)\leq{\varepsilon}^{2}$. Second, we use the following inequalities.

$s(\ell)\leq{\varepsilon}\cdot(1-s(C))\leq{\varepsilon}\cdot(1-s(P(C))).$ (80)

The first inequality is because $\ell\in\textsf{fit}(C)$. The second
inequality is by (79). Therefore, by (80) and that
$s(\ell)\leq{\varepsilon}^{2}$ we conclude that $\ell\in\textsf{fit}(P(C))$ by
(3).

  3. 3.

$|P(C)|=\left|\bigcup_{\Phi\in\mathcal{Q}}\textsf{last}_{|C\cap\Phi|}(\Phi)\right|\leq\sum_{\Phi\in\mathcal{Q}}|\textsf{last}_{|C\cap\Phi|}(\Phi)|=\sum_{\Phi\in\mathcal{Q}}|C\cap\Phi|\leq|C|\leq{\varepsilon}^{-10}.$

The first equality is by (13). The second equality is by the definition of
last. The second inequality is because each item in $C$ belongs to at most one
class in $\mathcal{Q}$. The last inequality is because
$C\in\textsf{supp}(\bar{y})$; thus, since $\bar{y}$ satisfies the conditions
of Lemma 3.7 it holds that $|C|\leq{\varepsilon}^{-10}$.

  4. 4.

First, there can be at most ${\varepsilon}^{-\upsilon-10}$ classes for each
important group $G\in{\mathcal{G}}_{\eta}\cup{\mathcal{A}}$ by Observation
5.2. Thus, the number of classes is bounded by
$|{\mathcal{G}}_{\eta}\cup{\mathcal{A}}|\cdot{\varepsilon}^{-\upsilon-10}$.
Second, by Claim D.1 we have a bound of $2K({\varepsilon})$ on the number for
important groups. By the above,

$\displaystyle|\mathcal{Q}|\leq{}$
$\displaystyle|{\mathcal{G}}_{\eta}\cup{\mathcal{A}}|\cdot{\varepsilon}^{-\upsilon-10}\leq
2K({\varepsilon})\cdot{\varepsilon}^{-\upsilon-10}=2{\varepsilon}^{-{\varepsilon}^{-2}}\cdot{\varepsilon}^{-3{\varepsilon}^{-2}-10}\leq{\varepsilon}^{-6{\varepsilon}^{-2}}$
(81)

The first inequality is by Claim D.1. Therefore,

$\displaystyle|\\{P(C^{\prime})~{}|~{}C^{\prime}\in\textsf{supp}(\bar{y})\\}|\leq{}$
$\displaystyle\left({\varepsilon}^{-10}|\mathcal{Q}|\right)^{{\varepsilon}^{-10}}\leq\left({\varepsilon}^{-{\varepsilon}^{-1}}\cdot{\varepsilon}^{-6{\varepsilon}^{-2}}\right)^{{\varepsilon}^{-10}}\leq\left({\varepsilon}^{-{\varepsilon}^{-3}}\right)^{{\varepsilon}^{-10}}\leq\left(\exp({\varepsilon}^{-1})^{{\varepsilon}^{-3}}\right)^{{\varepsilon}^{-10}}$
$\displaystyle\leq{}$
$\displaystyle\left(\exp({\varepsilon}^{-4})\right)^{{\varepsilon}^{-10}}\leq\exp({\varepsilon}^{-14})\leq\exp({\varepsilon}^{-14})+3K({\varepsilon})-3K({\varepsilon})$
$\displaystyle\leq{}$ $\displaystyle
2\cdot\exp({\varepsilon}^{-14})-3K({\varepsilon})\leq
Q({\varepsilon})-3K({\varepsilon}).$

Recall that for each $C^{\prime}\in\textsf{supp}(\bar{y})$ it holds that
$|C^{\prime}|\leq{\varepsilon}^{-10}$; in addition, by (13), for each item
$\ell\in P(C^{\prime})$ there is a single $\Phi\in\mathcal{Q}$ such that
$\ell\in\textsf{last}_{|C^{\prime}\cap\Phi|}(\Phi)$ and it follows that the
number of distinct options for choosing $\ell$ is bounded by
$|C^{\prime}\cap\Phi|\cdot|\mathcal{Q}|\leq|C^{\prime}|\cdot|\mathcal{Q}|\leq{\varepsilon}^{-10}\cdot|\mathcal{Q}|$.
Thus, by choosing at most ${\varepsilon}^{-10}$ items as described above, the
first inequality follows. The second inequality is by (81). The last
inequalities follow since $0<{\varepsilon}<0.1$,
$K({\varepsilon})={\varepsilon}^{-{\varepsilon}^{-2}}$ and
$Q({\varepsilon})=\exp\left({\varepsilon}^{-17}\right)$.

  5. 5.

Let $G\in{\mathcal{G}}$. Now,

$\displaystyle|G\cap P(C)|\leq{}$
$\displaystyle\left|\bigcup_{\Phi\in\mathcal{Q}\text{ s.t. }\Phi\subseteq
G}\textsf{last}_{|C\cap\Phi|}(\Phi)\right|=\sum_{\Phi\in\mathcal{Q}\text{ s.t.
}\Phi\subseteq G}\left|\textsf{last}_{|C\cap\Phi|}(\Phi)\right|$
$\displaystyle={}$ $\displaystyle\sum_{\Phi\in\mathcal{Q}\text{ s.t.
}\Phi\subseteq G}|C\cap\Phi|\leq|G\cap C|$

The first inequality is by (13). The second equality is because each item
belongs to at most one class. The third equality is because for all
$\Phi\in\mathcal{Q}$ the number of items in
$\textsf{first}_{|C\cap\Phi|}(\Phi)$ is the same as in $|C\cap\Phi|$ by the
definition of first. The last inequality is because by (13) every item in
$C\cap G$ belongs to at most one class and each class is a subset of some
group.

∎

In the following we prove Lemma 3.7. The proof relies on the following claims
and definitions and is given at the end of this section.

######  Claim D.2.

Algorithm 3 is runs in time
$\textnormal{poly}(\frac{1}{{\varepsilon}},|{\mathcal{I}}|)$.

###### Proof.

Finding the significant groups can be done in polynomial time by sorting the
groups according to the small item frequencies, where the the small item
frequency of a group can be computed in polynomial time as
$|\textsf{supp}(\bar{y})|$ is polynomial. In addition, finding the massive
groups, all groups with large items can be computed in linear time by
iterating over all groups. Thus, the construction of the important groups
takes polynomial time and therefore the constructing the classes in Step 3 can
be also achieved in polynomial time by (12). Furthermore, since
$|\textsf{supp}(\bar{y})|$ is polynomial, computing the projections of all
$C\in\textsf{supp}(\bar{y})$ is polynomial. Finally, the linear combinations
in Step 3 and Step 3 are of a polynomial number of elements; thus, they can be
computed in polynomial time. ∎

For convenience, we repeat the construction of $\bar{\lambda}$ as given in
Section 5. Recall that $\bar{\gamma}$ in the $\bar{y}$-polytope such that for
all $\ell,j\in I$, $\ell\neq j$ it holds that $\bar{\gamma}_{\ell,j}=0$. We
define below a point
$\bar{\lambda}\in\mathbb{R}^{I\times(I\cup\mathcal{C})}_{\geq 0}$ and show
that $\bar{\lambda}$ is in the $\bar{z}$-polytope. Thus, it follows that the
$\bar{z}$-polytope is non-empty. For all $C\in{\mathcal{C}}$, let
$P^{-1}(C)=\\{C^{\prime}\in{\mathcal{C}}~{}|~{}P(C^{\prime})=C\\}$. We start
with constructing a point
$\bar{\psi}\in\mathbb{R}^{I\times(I\cup\mathcal{C})}_{\geq 0}$, which is used
in the construction of $\bar{\lambda}$. For all $\ell\in I$ and
$C\in{\mathcal{C}}$ define

$\bar{\psi}_{\ell,C}=\sum_{C^{\prime}\in
P^{-1}(C)}\bar{\gamma}_{\ell,C^{\prime}}.$ (82)

Moreover, for any $G\in{\mathcal{G}}_{\eta}\cup{\mathcal{A}}$,
$i\in[\tau(G)-1]$, $\ell\in\Delta_{i+1}(G)$ and $j\in\Delta_{i}(G)$ define

$\bar{\psi}_{\ell,j}=\frac{f_{\bar{u}}(j)}{f_{\bar{u}}(\Delta_{i}(G))}\cdot\bar{\gamma}_{\ell,\ell}.$
(83)

For any other $\ell,j\in I$ define $\bar{\psi}_{\ell,j}=0$. We use the
following auxiliary claims.

######  Claim D.3.

$\bar{\psi}$ satisfies Constraint (4) of the $\bar{u}$-polytope.

###### Proof.

Let $\ell\in I$ and $t\in I\cup{\mathcal{C}}$ such that
$\bar{\psi}_{\ell,t}>0$. We split into two cases as follows.

  1. 1.

$t\in{\mathcal{C}}$. By (82), there exists $C\in P^{-1}(t)$ such that
$\bar{\gamma}_{\ell,C}>0$. Therefore, $\ell\in\textsf{fit}(C)$ by (4) since
$\bar{\gamma}$ is in the $\bar{y}$-polytope. Consequently, by Lemma 5.3 it
follows that $\ell\in\textsf{fit}(t)$.

  2. 2.

There are $G\in{\mathcal{G}}_{\eta}\cup{\mathcal{A}}$ and $i\in[\tau(G)-1]$
such that $t\in\Delta_{i}(G)$. By (83) it follows that
$\ell\in\Delta_{i+1}(G)$. Hence, $\ell\in\textsf{fit}(t)$ by Observation 5.2.

By the definition of $\bar{\psi}$, for any $\ell\in I$, the above cases cover
all possibilities for all $t\in I\cup{\mathcal{C}}$ such that
$\bar{\psi}_{\ell,t}>0$. ∎

######  Claim D.4.

$\bar{\psi}$ satisfies constraint (5) of the $\bar{u}$-polytope.

###### Proof.

Let $C\in\mathcal{C}$.

$\displaystyle\sum_{\ell\in I}\bar{\psi}_{\ell,C}\cdot s(\ell)={}$
$\displaystyle\sum_{\ell\in I~{}}\sum_{C^{\prime}\in
P^{-1}(C)}\bar{\gamma}_{\ell,C^{\prime}}\cdot s(\ell)=\sum_{C^{\prime}\in
P^{-1}(C)~{}}\sum_{\ell\in I}\bar{\gamma}_{\ell,C^{\prime}}\cdot s(\ell)$
$\displaystyle\leq{}$ $\displaystyle\sum_{C^{\prime}\in
P^{-1}(C)~{}}\left(1-s(C^{\prime})\right)\bar{y}_{C^{\prime}}\leq\sum_{C^{\prime}\in
P^{-1}(C)~{}}\left(1-s(C)\right)\bar{y}_{C^{\prime}}\leq\left(1-s(C)\right)\bar{u}_{C}.$

The first inequality is because $\bar{\gamma}$ is in the $\bar{y}$-polytope;
thus, the inequality follows by (5). The second inequality is because for all
$C^{\prime}\in\textsf{supp}(\bar{y})$ it holds that $s(P(C^{\prime}))\leq
s(C^{\prime})$ by Lemma 5.3. The last inequality is by Step 3 of Algorithm 3.

∎

######  Claim D.5.

$\bar{\psi}$ satisfies constraint (6) of the $\bar{u}$-polytope.

###### Proof.

Let $G\in\mathcal{G}$ and $C\in\mathcal{C}$.

$\displaystyle\sum_{\ell\in G}\bar{\psi}_{\ell,C}={}$
$\displaystyle\sum_{\ell\in G~{}}\sum_{C^{\prime}\in
P^{-1}(C)}\bar{\gamma}_{\ell,C^{\prime}}=\sum_{C^{\prime}\in
P^{-1}(C)~{}}\sum_{\ell\in
G}\bar{\gamma}_{\ell,C^{\prime}}\leq\sum_{C^{\prime}\in
P^{-1}(C)}\bar{y}_{C^{\prime}}\cdot\left(k(G)-|C^{\prime}\cap G|\right)$
$\displaystyle\leq{}$ $\displaystyle\left(k(G)-|C\cap
G|\right)\sum_{C^{\prime}\in
P^{-1}(C)}\bar{y}_{C^{\prime}}\leq\bar{u}_{C}\cdot\left(k(G)-|C\cap
G|\right).$

The first inequality is because $\bar{\gamma}$ is in the $\bar{y}$-polytope;
thus, the inequality follows by (6). The second inequality is by Property 5 of
Lemma 5.3.

∎

We use the following auxiliary claims.

######  Claim D.6.

For all $\Phi\in\mathcal{Q}$ it holds that
$f_{\bar{y}}(\Phi)\leq\frac{f_{\bar{u}}(\Phi)}{\left(1+\frac{2{\varepsilon}^{-\upsilon}}{\|\bar{y}\|}\right)}$.

###### Proof.

$\displaystyle f_{\bar{y}}(\Phi)={}$
$\displaystyle\sum_{\ell\in\Phi}f_{\bar{y}}(\ell)=\sum_{\ell\in\Phi~{}}\sum_{C\in{\mathcal{C}}[\ell]}\bar{y}_{C}=\sum_{C\in{\mathcal{C}}~{}}\sum_{\ell\in\Phi\cap
C}\bar{y}_{C}=\sum_{C\in{\mathcal{C}}~{}}|C\cap\Phi|\cdot\bar{y}_{C}$ (84)
$\displaystyle={}$
$\displaystyle\sum_{C\in{\mathcal{C}}~{}}\sum_{C^{\prime}\in
P^{-1}(C)~{}}|C^{\prime}\cap\Phi|\cdot\bar{y}_{C^{\prime}}=\sum_{C\in{\mathcal{C}}~{}}|C\cap\Phi|\sum_{C^{\prime}\in
P^{-1}(C)~{}}\bar{y}_{C^{\prime}}$ $\displaystyle\leq{}$
$\displaystyle\sum_{C\in{\mathcal{C}}~{}}|C\cap\Phi|\cdot\frac{\bar{u}_{C}}{\left(1+\frac{2{\varepsilon}^{-\upsilon}}{\|\bar{y}\|}\right)}=\frac{1}{\left(1+\frac{2{\varepsilon}^{-\upsilon}}{\|\bar{y}\|}\right)}\cdot\sum_{C\in{\mathcal{C}}~{}}|C\cap\Phi|\cdot\bar{u}_{C}.$

The sixth equality is because for all $C\in{\mathcal{C}}$ it holds that
$|C\cap\Phi|=|P(C)\cap\Phi|$ by (13). The last inequality is by Step 3 of
Algorithm 3. Additionally,

$\displaystyle f_{\bar{u}}(\Phi)={}$
$\displaystyle\sum_{\ell\in\Phi}f_{\bar{u}}(\ell)=\sum_{\ell\in\Phi~{}}\sum_{C\in{\mathcal{C}}[\ell]}\bar{u}_{C}=\sum_{C\in{\mathcal{C}}~{}}\sum_{\ell\in\Phi\cap
C}\bar{u}_{C}=\sum_{C\in{\mathcal{C}}~{}}|C\cap\Phi|\cdot\bar{u}_{C}$ (85)

The claim follows by (84) and (85). ∎

######  Claim D.7.

Let $G\in{\mathcal{G}}_{\eta}\cup{\mathcal{A}}$, $i\in[\tau(G)-1]$ and let
$j\in\Delta_{i}(G)$. It holds that $\sum_{\ell\in I}\bar{\psi}_{\ell,j}\leq
f_{\bar{u}}(j)$.

###### Proof.

$\displaystyle\sum_{\ell\in I}\bar{\psi}_{\ell,j}={}$
$\displaystyle\sum_{\ell\in\Delta_{i+1}(G)}\frac{f_{\bar{u}}(j)}{f_{\bar{u}}(\Delta_{i}(G))}\cdot\bar{\gamma}_{\ell,\ell}\leq\sum_{\ell\in\Delta_{i+1}(G)}\frac{f_{\bar{u}}(j)}{f_{\bar{u}}(\Delta_{i}(G))}\cdot
f_{\bar{y}}(\ell)\cdot=\frac{f_{\bar{u}}(j)}{f_{\bar{u}}(\Delta_{i}(G))}\cdot
f_{\bar{y}}(\Delta_{i+1}(G))$ $\displaystyle\leq{}$
$\displaystyle\frac{f_{\bar{u}}(j)}{f_{\bar{y}}(\Delta_{i}(G))\cdot\left(1+\frac{2{\varepsilon}^{-\upsilon}}{\|\bar{y}\|}\right)}\cdot{f_{\bar{y}}(\Delta_{i+1}(G))}{}\leq\frac{f_{\bar{u}}(j)}{{\varepsilon}^{\upsilon}\cdot\|\bar{y}\|\cdot\left(1+\frac{2{\varepsilon}^{-\upsilon}}{\|\bar{y}\|}\right)}\cdot{\left({\varepsilon}^{\upsilon}\cdot\|\bar{y}\|+2\right)}{}$
$\displaystyle=$ $\displaystyle
f_{\bar{u}}(j)=\sum_{C\in{\mathcal{C}}[j]}\bar{u}_{C}.$

The first equality is by (83). The second inequality is by Claim D.6. The
third inequality is by Observation 5.2.

∎

The following observation follows from Claim D.7, that cover the only case
where for some $\ell,j\in I$ it holds that $\bar{\psi}_{\ell,j}>0$ by (83).

######  Observation D.8.

$\bar{\psi}$ satisfies constraint (7) of the $\bar{u}$-polytope.

Proof of Claim 5.4: Claim 5.4 follows from Claim D.3, Claim D.4, Claim D.5,
and Observation D.8. ∎

We show below that $\psi$ satisfies constraint (8) for a specific subset of
the items, using the following auxiliary claims.

######  Claim D.9.

For all $\ell\in I$ it holds that
$\sum_{C\in{\mathcal{C}}}\bar{\psi}_{\ell,C}=\sum_{C\in{\mathcal{C}}}\bar{\gamma}_{\ell,C}$.

###### Proof.

$\displaystyle\sum_{C\in{\mathcal{C}}}\bar{\psi}_{\ell,C}={}$
$\displaystyle\sum_{C\in{\mathcal{C}}~{}}\sum_{C^{\prime}\in
P^{-1}(C)}\bar{\gamma}_{\ell,C^{\prime}}=\sum_{C^{\prime}\in{\mathcal{C}}~{}~{}}\sum_{C\in{\mathcal{C}}\text{
s.t.
}P(C^{\prime})=C}\bar{\gamma}_{\ell,C^{\prime}}=\sum_{C\in{\mathcal{C}}}\bar{\gamma}_{\ell,C}.$

∎

######  Claim D.10.

For all $G\in{\mathcal{G}}_{\eta}\cup{\mathcal{A}}$ and $\ell\in
G\setminus\Delta_{1}(G)$ it holds that $\sum_{t\in
I\cup{\mathcal{C}}}\bar{\psi}_{\ell,t}\geq 1$.

###### Proof.

by (83), there is $i\in\\{2,3,\ldots,\tau(G)\\}$ such that
$\ell\in\Delta_{i}(G)$. Therefore,

$\displaystyle\sum_{t\in I\cup{\mathcal{C}}}\bar{\psi}_{\ell,t}={}$
$\displaystyle\sum_{j\in\Delta_{i-1}(G)}\frac{f_{\bar{u}}(j)}{f_{\bar{u}}(\Delta_{i-1}(G))}\cdot\bar{\gamma}_{\ell,\ell}+\sum_{C\in{\mathcal{C}}}\bar{\psi}_{\ell,C}=\frac{\bar{\gamma}_{\ell,\ell}}{{f_{\bar{u}}(\Delta_{i-1}(G))}}\sum_{j\in\Delta_{i-1}(G)}f_{\bar{u}}(j)+\sum_{C\in{\mathcal{C}}}\bar{\psi}_{\ell,C}$
$\displaystyle={}$
$\displaystyle\frac{\bar{\gamma}_{\ell,\ell}}{{f_{\bar{u}}(\Delta_{i-1}(G))}}\cdot
f_{\bar{u}}(\Delta_{i-1}(G))+\sum_{C\in{\mathcal{C}}}\bar{\gamma}_{\ell,C}=\sum_{t\in
I\cup{\mathcal{C}}}\bar{\gamma}_{\ell,t}\geq 1.$

The first equality is by (83). The third equality is by Claim D.9. The fourth
equality is because for all $\ell\neq j\in I$ it holds that
$\bar{\gamma}_{\ell,j}=0$. The last inequality is because $\bar{\gamma}$ is in
the $\bar{y}$-polytope and thus satisfies property (8).

∎

We repeat the definition of $\bar{\mu}$ from Section 5. We define a point
$\bar{\mu}\in\mathbb{R}^{I}_{\geq 0}$ as follows. For all $\ell\in I$, define

$\bar{\mu}_{\ell}=\max\left\\{0,1-\sum_{t\in
I\cup{\mathcal{C}}}\bar{\psi}_{\ell,t}\right\\}.$ (86)

We prove below some properties of $\bar{\mu}$.

######  Claim D.11.

$\textnormal{{supp}}(\bar{\mu})\setminus
L\subseteq\textnormal{{fit}}(\emptyset)$.

###### Proof.

Let $\ell\in\textsf{supp}(\bar{\mu})\setminus L$. Thus, it follows that
$\ell\in I\setminus L$. Hence, $\ell\in\textsf{fit}(\emptyset)$ by (3). ∎

######  Claim D.12.

For all $\ell\in\textnormal{{supp}}(\bar{\mu})$ it holds that
$\ell\in\textnormal{{fit}}\left(r\left(\textnormal{{group}}(\ell)\right)\right)$.

###### Proof.

Let $\ell\in\textsf{supp}(\bar{\mu})$. Thus, by the definition of the maximal
slot $r\left(\textnormal{{group}}(\ell)\right)$ it holds that $s(\ell)\leq
s\left(r\left(\textnormal{{group}}(\ell)\right)\right)$ and that
$\textnormal{{group}}(\ell)=r\left(\textnormal{{group}}(\ell)\right)$. Hence,
the claim follows by (2). ∎

We use the following auxiliary claim.

######  Claim D.13.

For all $S\subseteq I$ it holds that $\sum_{\ell\in S}\bar{\mu}_{\ell}\leq
f_{\bar{y}}(S)$.

###### Proof.

$\displaystyle\sum_{\ell\in S}\bar{\mu}_{\ell}={}$ $\displaystyle\sum_{\ell\in
S}\max\left\\{0,1-\sum_{t\in
I\cup{\mathcal{C}}}\bar{\psi}_{\ell,t}\right\\}\leq\sum_{\ell\in
S}\max\left\\{0,1-\sum_{C\in{\mathcal{C}}}\bar{\psi}_{\ell,C}\right\\}=\sum_{\ell\in
S}\max\left\\{0,1-\sum_{C\in{\mathcal{C}}}\bar{\gamma}_{\ell,C}\right\\}$
$\displaystyle\leq{}$ $\displaystyle\sum_{\ell\in S}\max\left\\{0,\sum_{j\in
I}\bar{\gamma}_{\ell,j}\right\\}=\sum_{\ell\in
S}\bar{\gamma}_{\ell,\ell}\leq\sum_{\ell\in
S}f_{\bar{y}}(\ell)=f_{\bar{y}}(S).$

The second equality is by Claim D.9. The second inequality is because
$\bar{\gamma}$ is in the $\bar{y}$-polytope; thus, the inequality follows by
(8). ∎

######  Claim D.14.

For all $G\in{\mathcal{G}}_{\eta}\cup{\mathcal{A}}$ it holds that
$\sum_{\ell\in
G}\bar{\mu}_{\ell}\leq{\varepsilon}^{\upsilon}\cdot\|\bar{y}\|+2$.

###### Proof.

$\displaystyle\sum_{\ell\in
G}\bar{\mu}_{\ell}=\sum_{\ell\in\Delta_{1}(G)}\bar{\mu}_{\ell}\leq{}$
$\displaystyle
f_{\bar{y}}\left(\Delta_{1}(G)\right)\leq{\varepsilon}^{\upsilon}\cdot\|\bar{y}\|+2.$

The first equality is by Claim D.10 and (86). The first inequality is by Claim
D.13. The second inequality is by Observation 5.2. ∎

######  Claim D.15.

For all $G\in{\mathcal{G}}$ it holds that $\sum_{\ell\in
G}\bar{\mu}_{\ell}\leq{\varepsilon}\cdot\|\bar{y}\|+2$.

###### Proof.

We split the proof into two cases.

  1. 1.

$G\in{\mathcal{G}}_{\eta}\cup{\mathcal{A}}$. The claim follows by Claim D.14.

  2. 2.

$G\in{\mathcal{G}}\setminus({\mathcal{G}}_{\eta}\cup{\mathcal{A}})$. Then,

$\displaystyle\sum_{\ell\in G}\bar{\mu}_{\ell}={}$ $\displaystyle\sum_{\ell\in
G\setminus L}\bar{\mu}_{\ell}\leq f_{\bar{y}}\left(G\setminus
L\right)\leq{\varepsilon}\cdot\|\bar{y}\|\leq{\varepsilon}\cdot\|\bar{y}\|+2.$

The first equality is because $G\notin{\mathcal{A}}$; thus, it follows that
$L\cap G=\emptyset$ by (10). The first inequality is by Claim D.13. The second
inequality is by Lemma 5.1.

∎

######  Claim D.16.

$\sum_{\ell\in I\setminus L}\bar{\mu}_{\ell}\cdot
s(\ell)\leq{\varepsilon}\cdot\|\bar{y}\|$.

###### Proof.

We use the following inequalities. First,

$\displaystyle\sum_{\ell\in I\setminus L}\bar{\mu}_{\ell}\cdot s(\ell)={}$
$\displaystyle\sum_{\ell\in I\setminus L}\max\left\\{0,1-\sum_{t\in
I\cup{\mathcal{C}}}\bar{\psi}_{\ell,t}\right\\}\cdot s(\ell)$ (87)
$\displaystyle\leq{}$ $\displaystyle\sum_{\ell\in I\setminus
L}\max\left\\{0,1-\sum_{C\in{\mathcal{C}}}\bar{\psi}_{\ell,C}\right\\}\cdot
s(\ell)=\sum_{\ell\in I\setminus
L}\max\left\\{0,1-\sum_{C\in{\mathcal{C}}}\bar{\gamma}_{\ell,C}\right\\}\cdot
s(\ell)$

The last equality is by Claim D.9. Second,

$\displaystyle\sum_{\ell\in I\setminus
L}\max\left\\{0,1-\sum_{C\in{\mathcal{C}}}\bar{\gamma}_{\ell,C}\right\\}\cdot
s(\ell)\leq{}$ $\displaystyle\sum_{\ell\in I\setminus
L}\max\left\\{0,\sum_{j\in I}\bar{\gamma}_{\ell,j}\right\\}\cdot
s(\ell)=\sum_{\ell\in I\setminus L}\bar{\gamma}_{\ell,\ell}\cdot s(\ell)$ (88)
$\displaystyle\leq{}$ $\displaystyle\sum_{\ell\in I\setminus
L}f_{\bar{y}}(\ell)\cdot s(\ell)\leq{\varepsilon}\|\bar{y}\|.$

The first inequality is because $\bar{\gamma}$ is in the $\bar{y}$-polytope;
thus, the inequality follows by (8). The last inequality is by Lemma 5.1. The
claim follows by (87) and (88).

∎

Proof of Claim 5.5: The proof follows by Claim D.11, Claim D.15, and Claim
D.16. ∎

We Define another point
$\bar{\rho}\in\mathbb{R}^{I\times(I\cup\mathcal{C})}_{\geq 0}$ based on
$\bar{\mu}$. For all $\ell\in I\setminus L$ define
$\bar{\rho}_{\ell,\emptyset}=\bar{\mu}_{\ell}$; in addition, for all
$G\in{\mathcal{G}},\ell\in G$ define
$\bar{\rho}_{\ell,r(G)}=\bar{\mu}_{\ell}$; for any other entry $(\ell,t)\in
I\times\left(I\cup{\mathcal{C}}\right)$ define $\bar{\rho}_{\ell,t}=0$.
Finally, using the definitions of $\bar{\rho}$ and $\bar{\psi}$ we define:

$\bar{\lambda}=\bar{\rho}+\bar{\psi}.$ (89)

######  Claim D.17.

$\bar{\lambda}$ satisfies constraint (4) of the $\bar{z}$-polytope.

###### Proof.

Let $\ell\in I$ and $t\in I\cup{\mathcal{C}}$ such that
$\bar{\lambda}_{\ell,t}>0$. We split into three cases.

  1. 1.

$\ell\in I\setminus L$ and $\bar{\rho}_{\ell,t}>0$. By the definition of
$\bar{\rho}$ it follows that $t=\emptyset$. In addition,
$\bar{\rho}_{\ell,\emptyset}=\bar{\mu}_{\ell}$ and it follows that
$\ell\in\textsf{supp}(\bar{\mu})$. Therefore, by Lemma D.11 it holds that
$\ell\in\textsf{fit}(t)$.

  2. 2.

$\ell\in L$ and $\bar{\rho}_{\ell,t}>0$. By the definition of $\bar{\rho}$ it
follows that $t=r\left(\textsf{group}(\ell)\right)$. In addition,
$\bar{\rho}_{\ell,r\left(\textsf{group}(\ell)\right)}=\bar{\mu}_{\ell}$ and it
follows that $\ell\in\textsf{supp}(\bar{\mu})$. Therefore, by Lemma D.12 it
holds that $\ell\in\textsf{fit}(t)$.

  3. 3.

$\bar{\psi}_{\ell,t}>0$. It follows that $\ell\in\textsf{fit}(t)$ by Claim
5.4.

By (89), the above proves the claim. ∎

######  Claim D.18.

$\bar{\lambda}$ satisfies constraint (5) of the $\bar{z}$-polytope.

###### Proof.

Let $C\in{\mathcal{C}}$. We split into two cases.

  1. 1.

$C\neq\emptyset$.

$\displaystyle\sum_{\ell\in I}\bar{\lambda}_{\ell,C}\cdot s(\ell)={}$
$\displaystyle\sum_{\ell\in
I}\left(\bar{\rho}_{\ell,C}+\bar{\psi}_{\ell,C}\right)\cdot
s(\ell)=\sum_{\ell\in I}\bar{\psi}_{\ell,C}\cdot
s(\ell)\leq(1-s(C))\bar{u}_{C}\leq(1-s(C))\bar{z}_{C}.$

The second equality is because for all $\ell\in I$ and
$C^{\prime}\in{\mathcal{C}}\setminus\\{\emptyset\\}$ it holds that
$\bar{\rho}_{\ell,C^{\prime}}=0$. The first inequality is because $\bar{\psi}$
satisfies constraint (5) of the $\bar{u}$-polytope by Claim 5.4. The second
inequality is by Step 3 in Algorithm 3.

  2. 2.

$C=\emptyset$.

$\displaystyle\sum_{\ell\in I}\bar{\lambda}_{\ell,\emptyset}\cdot s(\ell)={}$
$\displaystyle\sum_{\ell\in
I}\left(\bar{\rho}_{\ell,\emptyset}+\bar{\psi}_{\ell,\emptyset}\right)\cdot
s(\ell)=\sum_{\ell\in I\setminus L}\bar{\mu}_{\ell}\cdot s(\ell)+\sum_{\ell\in
I}\bar{\psi}_{\ell,\emptyset}\cdot s(\ell)$ $\displaystyle\leq{}$
$\displaystyle{\varepsilon}\|\bar{y}\|+(1-s(\emptyset))\bar{u}_{\emptyset}={\varepsilon}\|\bar{y}\|+\bar{u}_{\emptyset}\leq\bar{z}_{\emptyset}=(1-s(\emptyset))\cdot\bar{z}_{\emptyset}.$

The first inequality is by Claim D.16 and because $\bar{\psi}$ satisfies
constraint (5) of the $\bar{u}$-polytope by Claim 5.4. The second inequality
is by Step 3 in Algorithm 3.

∎

######  Claim D.19.

$\bar{\lambda}$ satisfies constraint (6) of the $\bar{z}$-polytope.

###### Proof.

Let $G\in{\mathcal{G}}$ and $C\in{\mathcal{C}}$. We split into two cases.

  1. 1.

$C\neq\emptyset$.

$\displaystyle\sum_{\ell\in G}\bar{\lambda}_{\ell,C}=\sum_{\ell\in
G}\left(\bar{\rho}_{\ell,C}+\bar{\psi}_{\ell,C}\right)=\sum_{\ell\in
G}\bar{\psi}_{\ell,C}\leq\bar{u}_{C}\cdot\left(k(G)-|G\cap
C|\right)\leq\bar{z}_{C}\cdot\left(k(G)-|G\cap C|\right).$

The second equality is because for all $\ell\in I$ and
$C^{\prime}\neq\emptyset$ it holds that $\bar{\rho}_{\ell,C^{\prime}}=0$. The
first inequality is because $\bar{\psi}$ satisfies constraint (6) of the
$\bar{u}$-polytope by Claim 5.4. The second inequality is by Step 3 in
Algorithm 3.

  2. 2.

$C=\emptyset$.

$\displaystyle\sum_{\ell\in G}\bar{\lambda}_{\ell,\emptyset}={}$
$\displaystyle\sum_{\ell\in
G}\left(\bar{\rho}_{\ell,\emptyset}+\bar{\psi}_{\ell,\emptyset}\right)=\sum_{\ell\in
G\setminus L}\bar{\mu}_{\ell}+\sum_{\ell\in
G}\bar{\psi}_{\ell,\emptyset}\leq{\varepsilon}\cdot\|\bar{y}\|+2+\bar{u}_{\emptyset}\cdot
k(G)$ $\displaystyle\leq{}$
$\displaystyle\left({\varepsilon}\|\bar{y}\|+2\right)\cdot
k(G)+\bar{u}_{\emptyset}\cdot k(G)\leq\bar{z}_{\emptyset}\cdot k(G).$

The first inequality is by Claim D.15 and because $\bar{\psi}$ satisfies
constraint (6) of the $\bar{u}$-polytope by Claim 5.4. The last inequality is
by Step 3 in Algorithm 3.

∎

######  Claim D.20.

$\bar{\lambda}$ satisfies constraint (7) of the $\bar{z}$-polytope.

###### Proof.

Let $j\in I$. We split into two cases, as follows.

  1. 1.

If $\textsf{group}(j)\in{\mathcal{G}}_{\eta}\cup{\mathcal{A}}$ and
$j=r\left(\textsf{group}(j)\right)$. Then,

$\displaystyle\sum_{\ell\in I}\bar{\lambda}_{\ell,j}=\sum_{\ell\in
I}\left(\bar{\rho}_{\ell,j}+\bar{\psi}_{\ell,j}\right)=\sum_{\ell\in\textsf{group}(j)}\bar{\mu}_{\ell,j}+\sum_{\ell\in
I}\bar{\psi}_{\ell,j}\leq{\varepsilon}^{\upsilon}\cdot\|\bar{y}\|+2+\sum_{C\in{\mathcal{C}}[j]}\bar{u}_{C}\leq\sum_{C\in{\mathcal{C}}[j]}\bar{z}_{C}.$

The first inequality is by Claim D.14 and because $\bar{\psi}$ satisfies
constraint (7) of the $\bar{u}$-polytope by Claim 5.4. The second inequality
is by Step 3 in Algorithm 3.

  2. 2.

Otherwise,

$\sum_{\ell\in I}\bar{\lambda}_{\ell,j}=\sum_{\ell\in
I}\left(\bar{\rho}_{\ell,j}+\bar{\psi}_{\ell,j}\right)=\sum_{\ell\in
I}\bar{\psi}_{\ell,j}\leq\sum_{C\in{\mathcal{C}}[j]}\bar{u}_{C}\leq\sum_{C\in{\mathcal{C}}[j]}\bar{z}_{C}.$

The first inequality is because $\bar{\psi}$ satisfies constraint (7) of the
$\bar{u}$-polytope by Claim 5.4. The second inequality is by Step 3 in
Algorithm 3.

∎

######  Claim D.21.

$\bar{\lambda}$ satisfies constraint (8) of the $\bar{z}$-polytope.

###### Proof.

Let $\ell\in I$.

$\sum_{t\in I\cup{\mathcal{C}}}\bar{\lambda}_{\ell,t}=\sum_{t\in
I\cup{\mathcal{C}}}\left(\bar{\rho}_{\ell,j}+\bar{\psi}_{\ell,t}\right)=\bar{\mu}_{\ell}+\sum_{t\in
I\cup{\mathcal{C}}}\bar{\psi}_{\ell,t}=\max\left\\{0,1-\sum_{t\in
I\cup{\mathcal{C}}}\bar{\psi}_{\ell,t}\right\\}+\sum_{t\in
I\cup{\mathcal{C}}}\bar{\psi}_{\ell,t}\geq 1.$

∎

The following observation follows by Claim D.17, Claim D.18, Claim D.19, Claim
D.20, and Claim D.21.

Proof of Claim 5.6: The proof follows by Claim D.17, Claim D.18, Claim D.19,
Claim D.20, and Claim D.21. ∎

######  Claim D.22.

Algorithm 3 returns a prototype $\bar{z}$ of $\mathcal{I}$ such that
$|\textnormal{{supp}}(\bar{z})|\leq Q({\varepsilon})$.

###### Proof.

$\displaystyle|\textsf{supp}(\bar{z})|\leq{}$
$\displaystyle|\\{P(C)~{}|~{}C\in\textsf{supp}(\bar{y})\\}|+1+|{\mathcal{G}}_{\eta}\cup{\mathcal{A}}|$
$\displaystyle\leq{}$ $\displaystyle
Q({\varepsilon})-3K({\varepsilon})+|{\mathcal{G}}_{\eta}\cup{\mathcal{A}}|+1\leq
Q({\varepsilon})-3K({\varepsilon})+2K({\varepsilon})+1\leq Q({\varepsilon}).$

The first inequality is because for all $C\in\textsf{supp}(\bar{z})$ either
$C=\emptyset$, there is $G\in{\mathcal{G}}_{\eta}\cup{\mathcal{A}}$ such that
$C=r(G)$, or there is $C^{\prime}\in\textsf{supp}(\bar{y})$ such that
$P(C^{\prime})=C$ by Step 3 and Step 3 of Algorithm 3. The second inequality
is by Lemma 5.3. The third inequality is by Claim D.1. ∎

######  Claim D.23.

Algorithm 3 returns a prototype $\bar{z}$ of $\mathcal{I}$ such that
$\|\bar{z}\|\leq(1+5{\varepsilon})\|\bar{y}\|+Q({\varepsilon})$.

###### Proof.

We use the following inequalities.

$\displaystyle\left\|\sum_{G\in{\mathcal{G}}_{\eta}\cup{\mathcal{A}}}\left({\varepsilon}^{\upsilon}\cdot\|\bar{y}\|+2\right)\cdot\mathbb{I}^{r(G)}\right\|\leq{}$
$\displaystyle\sum_{G\in{\mathcal{G}}_{\eta}\cup{\mathcal{A}}}\left({\varepsilon}^{\upsilon}\cdot\|\bar{y}\|+2\right)\cdot\|\mathbb{I}^{r(G)}\|$
(90) $\displaystyle={}$
$\displaystyle|{\mathcal{G}}_{\eta}\cup{\mathcal{A}}|\cdot({\varepsilon}^{\upsilon}\cdot\|\bar{y}\|+2)\leq
2K({\varepsilon})\cdot({\varepsilon}^{\upsilon}\cdot\|\bar{y}\|+2)$
$\displaystyle\leq{}$
$\displaystyle{\varepsilon}^{-2{\varepsilon}^{-2}}\cdot{\varepsilon}^{3{\varepsilon}^{-2}}\cdot\|\bar{y}\|+4K({\varepsilon})$
$\displaystyle\leq{}$
$\displaystyle{\varepsilon}\cdot\|\bar{y}\|+4K({\varepsilon}).$

The first inequality is by the triangle inequality. The second inequality is
by Claim D.1.

$\displaystyle\left\|\left(4{\varepsilon}\|\bar{y}\|+{\varepsilon}^{-3}\right)\cdot\mathbb{I}^{\emptyset}+\left(1+\frac{2{\varepsilon}^{-\upsilon}}{\|\bar{y}\|}\right)\sum_{C\in\textsf{supp}(\bar{y})}\bar{y}_{C}\cdot\mathbb{I}^{P(C)}\right\|$
(91) $\displaystyle\leq{}$
$\displaystyle\left\|\left(4{\varepsilon}\|\bar{y}\|+{\varepsilon}^{-3}\right)\
\cdot\mathbb{I}^{\emptyset}\right\|+\left(1+\frac{2{\varepsilon}^{-\upsilon}}{\|\bar{y}\|}\right)\left\|\sum_{C\in\textsf{supp}(\bar{y})}\bar{y}_{C}\cdot\mathbb{I}^{P(C)}\right\|$
$\displaystyle\leq{}$
$\displaystyle\left(4{\varepsilon}\|\bar{y}\|+{\varepsilon}^{-3}\right)\cdot\|\mathbb{I}^{\emptyset}\|+\left(1+\frac{2{\varepsilon}^{-\upsilon}}{\|\bar{y}\|}\right)\sum_{C\in\textsf{supp}(\bar{y})}\bar{y}_{C}\cdot\|\mathbb{I}^{P(C)}\|$
$\displaystyle={}$ $\displaystyle
4{\varepsilon}\|\bar{y}\|+{\varepsilon}^{-3}+\left(1+\frac{2{\varepsilon}^{-\upsilon}}{\|\bar{y}\|}\right)\|\bar{y}\|=(1+4{\varepsilon})\cdot\|\bar{y}\|+2{\varepsilon}^{-\upsilon}+{\varepsilon}^{-3}$

The first inequality is by the triangle inequality. The third equality is
since for all $C\in{\mathcal{C}}$ it holds that $\|\mathbb{I}^{C}\|=1$ by the
definition of the indicator of $C$. Now,

$\displaystyle\|\bar{z}\|\leq{}$
$\displaystyle\left\|\sum_{G\in{\mathcal{G}}_{\eta}\cup{\mathcal{A}}}\left({\varepsilon}^{\upsilon}\cdot\|\bar{y}\|+2\right)\cdot\mathbb{I}^{r(G)}+\left(4{\varepsilon}\|\bar{y}\|+{\varepsilon}^{-3}\right)\cdot\mathbb{I}^{\emptyset}+\left(1+\frac{2\cdot{\varepsilon}^{-\upsilon}}{\|\bar{y}\|}\right)\sum_{C\in\textsf{supp}(\bar{y})}\bar{y}_{C}\cdot\mathbb{I}^{P(C)}\right\|$
$\displaystyle\leq{}$
$\displaystyle{\varepsilon}\cdot\|\bar{y}\|+4K({\varepsilon})+(1+4{\varepsilon})\cdot\|\bar{y}\|+2{\varepsilon}^{-v}+{\varepsilon}^{-3}\leq(1+5{\varepsilon})\cdot\|\bar{y}\|+7{\varepsilon}^{-3{\varepsilon}^{-2}}$
$\displaystyle\leq{}$
$\displaystyle(1+5{\varepsilon})\cdot\|\bar{y}\|+Q({\varepsilon}).$

The first equality is by Step 3 and Step 3 of Algorithm 3. The second
inequality is by the triangle inequality and by (90) and (91). The last
inequalities are because ${\varepsilon}<0.1$,
$K({\varepsilon})={\varepsilon}^{-{\varepsilon}^{-2}}$ and
$Q({\varepsilon})=\exp({\varepsilon}^{-17})$.

∎

######  Claim D.24.

Algorithm 3 returns a prototype $\bar{z}$ of $\mathcal{I}$ such that for all
$C\in\textnormal{ {supp}}(\bar{z})$ it holds that
$|C|\leq{\varepsilon}^{-10}$.

###### Proof.

Let $C\in\textsf{supp}(\bar{z})$ be a configuration. If $C=\emptyset$ or there
is $G\in{\mathcal{G}}_{\eta}\cup{\mathcal{A}}$ such that $C=r(G)$ that
contains a single item, then the claim is trivial. Otherwise, because
$C\in\textsf{supp}(\bar{z})$, then by Step 3 of Algorithm 3, there is
$C^{\prime}\in\textsf{supp}(\bar{y})$ such that $P(C^{\prime})=C$. Therefore,
$|C|=|P(C^{\prime})|\leq{\varepsilon}^{-10}$ by Lemma 5.3. ∎

Proof of Lemma 3.7: The proof follows by Claim D.2, Claim 5.6, Claim D.22,
Claim D.23, and Claim D.24. ∎

##  Appendix E Omitted Proofs of Section 6

Proof of Lemma 6.2: For all $\ell\in U$, let $d(\ell)=|\\{v\in
V~{}|~{}(\ell,v)\in E\\}|$ be the degree of $\ell$ in $G$. For all $\ell\in U$
there is exactly one $j\in I$ such that $\bar{\gamma}_{\ell,j}=1$ because
$\bar{\gamma}$ satisfies constraint (8) of the $\bar{z}^{*}$-polytope with
equality; let $\ell^{*}=j$. Therefore, for every $\ell\in U$ it holds:

$d(\ell)=|\\{(C,\ell^{*},k)\in V~{}|~{}(\ell,(C,\ell^{*},k))\in
E\\}|=\sum_{C\in{\mathcal{C}}[\ell^{*}]~{}}\sum_{k\in[\bar{z}^{*}_{C}]}1=\sum_{C\in{\mathcal{C}}[\ell^{*}]}\bar{z}^{*}_{C}\geq\sum_{\ell^{\prime}\in
I}\bar{\gamma}_{\ell^{\prime},\ell^{*}}\geq\bar{\gamma}_{\ell,\ell^{*}}=1.$
(92)

The first inequality is because $\bar{\gamma}$ is in the
$\bar{z}^{*}$-polytope. Define a fractional matching as a vector
$\bar{M}\in[0,1]^{E}$ such that for all $(\ell,v)\in E$ define
$\bar{M}_{(\ell,v)}=\frac{1}{d(\ell)}$; note that $\bar{M}$ is well-defined
(i.e., for all $\ell\in U$ it holds that $d(\ell)>0$) by (92). We show below
that $\bar{M}$ is a fractional matching in $G$ of size $|U|$.

  1. 1.

$\bar{M}$ is a feasible fractional matching in $G$. Let $\ell^{\prime}\in U$.
It holds that:

$\sum_{(\ell^{\prime},v)\in
E}\bar{M}_{(\ell^{\prime},v)}=\sum_{(\ell^{\prime},v)\in
E}\frac{1}{d(\ell)}=d(\ell)\cdot\frac{1}{d(\ell)}=1.$

In addition, let $(C,j,k)\in V$ and let $v=(C,j,k)$. It holds that:

$\displaystyle\sum_{(\ell,v)\in E}\bar{M}_{(\ell,v)}={}$
$\displaystyle\sum_{(\ell,v)\in E}\frac{1}{d(\ell)}=\sum_{\ell\in U\text{ s.t.
}\bar{\gamma}_{\ell,j}=1}\frac{1}{d(\ell)}\leq\sum_{\ell\in U\text{ s.t.
}\bar{\gamma}_{\ell,j}=1}\bar{\gamma}_{\ell,j}\cdot\frac{1}{d(\ell)}$
$\displaystyle\leq{}$ $\displaystyle\sum_{\ell\in U\text{ s.t.
}\bar{\gamma}_{\ell,j}=1}\bar{\gamma}_{\ell,j}\cdot\frac{1}{\sum_{\ell^{\prime}\in
I}\bar{\gamma}_{\ell^{\prime},j}}\leq\frac{1}{\sum_{\ell^{\prime}\in
I}\bar{\gamma}_{\ell^{\prime},j}}\cdot\sum_{\ell\in
I}\bar{\gamma}_{\ell,j}=1.$

The second inequality is by (92). By the above, we conclude that $\bar{M}$ is
a feasible fractional matching in $G$.

  2. 2.

$|\bar{M}|=|U|$.

$|\bar{M}|=\sum_{e\in E}\bar{M}_{e}=\sum_{\ell\in U}\sum_{(\ell,v)\in
E}\bar{M}_{e}=\sum_{\ell\in U}\sum_{(\ell,v)\in
E}\frac{1}{d(\ell)}=\sum_{\ell\in U}\frac{d(\ell)}{d(\ell)}=|U|.$

By the above, $\bar{M}$ is a fractional matching in $G$ with size $|U|$. Since
$G$ is a bipartite graph, there is an integral matching with size $|U|$ in $G$
[45]. ∎

Proof of Lemma 6.3: For all $\ell\in A_{C,k}$ there is exactly one $j\in C$
such that $(\ell,(C,j,k))\in M$ by the definition of $A_{C,k}$ and because $M$
is a matching; we define $\ell^{*}=j$ to be the slot of  $\ell$. We construct
an injective function $\sigma:A_{C,k}\rightarrow C$ such that for all $\ell\in
A_{C,k}$ define $\sigma(\ell)=\ell^{*}$. By the above, for all $\ell\in
A_{C,k}$ it holds that $\ell^{*}$ is well defined and it follows that $\sigma$
is a function. Let $\ell_{1},\ell_{2}\in A_{C,k}$ such that
$\ell_{1}\neq\ell_{2}$. Since $M$ is a matching, it follows that
$\ell^{*}_{1}\neq\ell^{*}_{2}$; hence, $\sigma(\ell_{1})\neq\sigma(\ell_{2})$
and we conclude that $\sigma$ is injective. Finally, let $\ell\in A_{C,k}$.
Since $(\ell,(C,\ell^{*},k))\in M$, by the definition of $E$ it follows that
$\bar{\gamma}_{\ell,\ell^{*}}=1$; thus, $\ell\in\textsf{fit}(\ell^{*})$ by (4)
since $\bar{\gamma}$ is in the $\bar{y}$-polytope. ∎

Proof of Claim 6.4: We prove the three properties of the claim below.

  1. 1.

$D_{C}\subseteq\textsf{fit}(C)$: Let $\ell\in D_{C}$. By the definition of
$D_{C}$ it holds that $\bar{\gamma}_{\ell,C}=1$, and in particular
$\bar{\gamma}_{\ell,C}>0$; thus, since $\bar{\gamma}$ is in the
$\bar{z}^{*}$-polytope it follows by (4) that $\ell\in\textsf{fit}(C)$.

  2. 2.

$s(D_{C})\leq\left(1-s(C)\right)\cdot|B_{C}|$:

$s(D_{C})=\sum_{\ell\in I\text{ s.t.
}\bar{\gamma}_{\ell,C}=1}s(\ell)=\sum_{\ell\in I\text{ s.t.
}\bar{\gamma}_{\ell,C}=1}\bar{\gamma}_{\ell,C}\cdot s(\ell)\leq\sum_{\ell\in
I}\bar{\gamma}_{\ell,C}\cdot
s(\ell)\leq(1-s(C))\bar{z}^{*}_{C}\leq\left(1-s(C)\right)\cdot|B_{C}|.$

The second inequality is because $\bar{\gamma}$ is in the
$\bar{z}^{*}$-polytope; thus, the inequality follows by (5). The last
inequality is by (15).

  3. 3.

$|D_{C}\cap G|\leq|B_{C}|\cdot\left(k(G)-|G\cap C|\right)$:

$\displaystyle|D_{C}\cap G|={}$ $\displaystyle\left|\bigcup_{\ell\in I\text{
s.t. }\bar{\gamma}_{\ell,C}=1}\\{\ell\\}\cap G\right|\leq\sum_{\ell\in I\text{
s.t. }\bar{\gamma}_{\ell,C}=1}\left|\\{\ell\\}\cap G\right|=\sum_{\ell\in
G\text{ s.t. }\bar{\gamma}_{\ell,C}=1}\left|\\{\ell\\}\right|$
$\displaystyle={}$ $\displaystyle\sum_{\ell\in G\text{ s.t.
}\bar{\gamma}_{\ell,C}=1}\bar{\gamma}_{\ell,C}\leq\sum_{\ell\in
G}\bar{\gamma}_{\ell,C}\leq\bar{z}^{*}_{C}\cdot\left(k(G)-|G\cap
C|\right)\leq|B_{C}|\cdot\left(k(G)-|G\cap C|\right).$

The third inequality is because $\bar{\gamma}$ is in the
$\bar{z}^{*}$-polytope; thus, the inequality follows by (6). The last
inequality is by (15). ∎

Proof of Lemma 6.5: We divide the proof of Lemma 6.5 to the following claims.
For simplicity, let $A^{*}=(A_{1},\ldots,A_{m})$.

######  Claim E.1.

$A^{*}$ is a packing.

###### Proof.

Let $i\in[m]$. By (14), we split into two cases.

  1. 1.

$A_{i}\in F$. Then, by the definition of $F$ it holds that $A_{i}$ is a
singleton, a set containing a single item. Thus, $s\left(A_{i}\right)\leq 1$
and for all $G\in{\mathcal{G}}$ it holds that $|G\cap A^{*}_{b}|\leq 1\leq
k(G)$.

  2. 2.

There are $C\in C^{*}$ and $k\in[\bar{z}^{*}_{C^{*}}]$ such that
$A_{i}=A_{C,k}$. Therefore, by Lemma 6.3 it holds that $A^{*}_{b}$ is allowed
in $C$. Hence, there is an injective function $\sigma:A_{i}\rightarrow C$ such
that for all $\ell\in A_{i}$ it holds that
$\ell\in\textsf{fit}\left(\sigma(\ell)\right)$. Therefore,

    1. (a)

$s(A_{i})\leq 1$.

$s(A_{i})=\sum_{\ell\in A_{i}}s(\ell)\leq\sum_{\ell\in
A_{i}}s\left(\sigma(\ell)\right)\leq\sum_{\ell\in C}s(\ell)=s(C)\leq 1.$

The first inequality is because for all $\ell\in A_{i}$ it holds that
$\ell\in\textsf{fit}\left(\sigma(\ell)\right)$; thus, the inequality follows
by (2). The second inequality is because $\sigma$ is injective. The last
inequality is because $C$ is a configuration.

    2. (b)

For all $G\in{\mathcal{G}}$ it holds that $|A_{i}\cap G|\leq k(G)$. Let
$G\in{\mathcal{G}}$. Now,

$|A_{i}\cap G|=\left|\bigcup_{\ell\in A_{i}}\\{\ell\\}\cap
G\right|=\bigcup_{\ell\in A_{i}}\left|\\{\ell\\}\cap
G\right|\leq\bigcup_{\ell\in A_{i}}\left|\\{\sigma(\ell)\\}\cap
G\right|\leq\left|\bigcup_{\ell\in C}\\{\ell\\}\cap G\right|=|C\cap G|\leq
k(G).$

The first inequality is because $\sigma$ is injective and that $G\cap
M=\emptyset$; thus, by (2) for all $\ell\in A_{i}\cap G$ it holds that
$\sigma(\ell)\in A_{i}\cap G$. The second inequality is because $\sigma$ is
injective. The last inequality is because $C$ is a configuration.

∎

######  Claim E.2.

$|\mathcal{H}|\leq{\varepsilon}^{-22}Q^{2}({\varepsilon})$

###### Proof.

$|\mathcal{H}|=\left|\textsf{supp}(\bar{z}^{*})\cup
F\right|\leq\left|\textsf{supp}(\bar{z}^{*})\right|+\left|F\right|\leq|\textsf{supp}(\bar{z}^{*})|+{\varepsilon}^{-21}|\textsf{supp}(\bar{z}^{*})|^{2}\leq{\varepsilon}^{-22}|\textsf{supp}(\bar{z})|^{2}\leq{\varepsilon}^{-22}Q^{2}({\varepsilon}).$

The second inequality is because $\bar{z}^{*}$ holds the conditions of Lemma
3.9 by Observation 6.1; thus, the inequality follows by Lemma 3.4. The third
inequality is because $0<{\varepsilon}<0.1$ and by Observation 6.1. The last
inequality is because $\bar{z}$ holds the conditions of Lemma 3.9, that is,
$\bar{z}$ is a good prototype. ∎

######  Claim E.3.

The size of $\mathcal{B}$ is at most
$\|\bar{z}\|+{\varepsilon}^{-22}|\textnormal{{supp}}(\bar{z})|^{2}$.

###### Proof.

The size of $\mathcal{B}$ is defined as the number of entries in $A^{*}$.
Therefore, by (14) the size of $\mathcal{B}$ is at most:

$\displaystyle|F|+\sum_{C\in\textsf{supp}(\bar{z}^{*})}\sum_{k\in[\bar{z}^{*}_{C}]}={}$
$\displaystyle|F|+\sum_{C\in\textsf{supp}(\bar{z}^{*})}\bar{z}^{*}_{C}\leq\|\bar{z}^{*}\|+{\varepsilon}^{-21}|\textsf{supp}(\bar{z}^{*})|^{2}$
$\displaystyle\leq{}$
$\displaystyle\|\bar{z}\|+|\textsf{supp}(\bar{z})|+{\varepsilon}^{-21}|\textsf{supp}(\bar{z})|^{2}\leq\|\bar{z}\|+{\varepsilon}^{-22}|\textsf{supp}(\bar{z})|^{2}\leq\|\bar{z}\|+{\varepsilon}^{-22}Q^{2}({\varepsilon}).$

The first inequality is because $\bar{z}^{*}$ holds the conditions of Lemma
3.9 by Observation 6.1; thus, the inequality follows by Lemma 3.4. The second
inequality is by Observation 6.1. The last inequality is because $\bar{z}$ is
a good prototype.

∎

######  Claim E.4.

$\\{B_{C}\\}_{C\in\mathcal{H}}$ is a partition of $\\{A_{i}~{}|~{}i\in[m]\\}$

###### Proof.

Let $i\in[m]$. By (14), we split into two cases.

  1. 1.

$A_{i}\in F$. Then, by the definition of $\mathcal{H}$ it holds that
$A_{i}\in\mathcal{H}$; thus, by (15) it follows that $A_{i}\in B_{A_{i}}$ and
for all $C\in\mathcal{H}\setminus\\{A_{i}\\}$ it holds that $A_{i}\notin
B_{C}$.

  2. 2.

There are $C\in\mathcal{H}$ and $k\in[\bar{z}^{*}_{C}]$ such that
$A_{i}=A_{C,k}$. Therefore, by (15) it follows that $A_{i}\in B_{C}$ and for
all $C^{\prime}\in\mathcal{H}\setminus\\{C\\}$ it holds that $A_{i}\notin
B_{C^{\prime}}$.

∎

Let $f=\\{\ell~{}|~{}\\{\ell\\}\in F\\}$ be all fractional items. We use the
following auxiliary claim.

######  Claim E.5.

$A^{*}$ is a packing of $f\cup U$.

###### Proof.

Let $\ell\in U\cup f$. We split into two cases.

  1. 1.

$\ell\in f$. By (14), there is $i\in[m]$ such that $A_{i}=\\{\ell\\}$.

  2. 2.

$\ell\in U$. Since $M$ is a matching of size $|U|$ in $G$, there is
$(C,j,k)\in V$ such that $(\ell,(C,j,k))\in M$. Therefore, by the definition
of the bin of $C$ and $k$ it holds that $\ell\in A_{C,k}$. Hence, by (14)
there is $i\in[m]$ such that $A_{i}=A_{C,k}$ and the claim follows.

Moreover, by (14) it follows that for any $\ell\in I\setminus(U\cup f)$ and
$i\in[m]$ it holds that $\ell\notin A_{i}$. ∎

######  Claim E.6.

$\\{D_{C}\\}_{C\in\mathcal{H}}$ is a partition of
$I\setminus\bigcup_{i\in[m]}A_{i}$.

###### Proof.

Let $\ell\in I\setminus\bigcup_{i\in[m]}A_{i}$. By Claim E.5, it follows that
$I\setminus\bigcup_{i\in[m]}A_{i}=I\setminus(U\cup f)$ and we get $\ell\in
I\setminus(U\cup f)$. Thus, as $\ell$ is not fractional and is not fully
assigned to a slot type as it is not in $U$, it follows that there is
$C\in\textsf{supp}(\bar{z}^{*})$ such that $\bar{\gamma}_{\ell,C}=1$ by (8)
since $\bar{\gamma}$ is in the $\bar{z}^{*}$-polytope. In addition, since (8)
holds with equality, we get that there is exactly one such $C$. Since
$\textsf{supp}(\bar{z}^{*})\subseteq\mathcal{H}$, it follows that $\ell\in
D_{C}$ and for all $C^{\prime}\in\mathcal{H}\setminus\\{C\\}$ it holds that
$\ell\notin D_{C^{\prime}}$. Hence, the claim follows.

∎

######  Claim E.7.

For any $C\in\mathcal{H}$ and $A\in B_{C}$ it holds that $A$ is allowed in $C$

###### Proof.

By Claim E.4, there is $i\in[m]$ such that $A=A_{i}$. By (14), we split into
two cases.

  1. 1.

$A_{i}\in F$. Then, by (15) it holds that $A_{i}=C$ and $C$ is a singleton.
Then, it trivially follows that $A_{i}$ is allowed in $A_{i}$, since for each
item $\ell\in A_{i}$ it holds that $\ell\in\textsf{fit}(\ell)$ by (2).

  2. 2.

There are $C\in\mathcal{H}$ and $k\in[\bar{z}^{*}_{C}]$ such that
$A_{i}=A_{C,k}$. Therefore, by Lemma 6.3 the claim follows.

∎

The proof of Lemma 6.5 follows by Claim E.1, Claim E.2, Claim E.3, Claim E.4,
Claim E.6, Claim E.7, and Claim 6.4. ∎

##  Appendix F Omitted Proofs of Section 7

We use the following auxiliary claim.

######  Claim F.1.

For all $C\in\mathcal{H}$ and $\ell\in D_{C}$ it holds that $s_{C}(\ell)<0.1$.

###### Proof.

$s_{C}(\ell)=\frac{s(\ell)}{1-s(C)}\leq\frac{{\varepsilon}\cdot(1-s(C))}{1-s(C)}={\varepsilon}<0.1.$

The first equality is by (16). The first inequality is because
$\ell\in\textsf{fit}(C)$ by Definition 3.8; hence, the inequality follows by
(3). ∎

Proof of Lemma 7.1: Let
$X=\textsf{tuple}(B_{C}),Y=\textsf{Greedy}({\mathcal{I}}_{C},{\varepsilon})$,
$X=(X_{1},\ldots,X_{r})$, $Y=(Y_{1},\ldots,Y_{t})$, $S=D_{C}\cup\bigcup_{B\in
B_{C}}B$, $Z=X+Y$, and $Z=(Z_{1},\ldots,Z_{p})$. We prove the following.

  1. 1.

$Z$ is a partition of $S$. Let $\ell\in S$. If $\ell\in D_{C}$, then there is
$i\in[r]$ such that $\ell\in X_{i}$; therefore, by the definition of $Z$ it
holds that $\ell\in Z_{i}$. Otherwise, there is $i\in[t]$ such that $\ell\in
Y_{i}$; therefore, by the definition of $Z$ it holds that $\ell\in Z_{i}$.

  2. 2.

For all $i\in[p]$ it holds that $s(Z_{i})\leq 1$. If $D_{C}=\emptyset$ then
the claim is satisfied because $s(Z_{i})=s(X_{i})\leq s(C)\leq 1$; The first
inequality is because $X_{i}\in B_{C}$ and thus $X_{i}$ is allowed in $C$; The
second inequality is because $C$ is a configuration. Otherwise, If $i\leq t$
and $i\leq r$:

$s(Z_{i})=s(X_{i})+s(Y_{i})\leq s(C)+s(Y_{i})\leq s(C)+(1-s(C))\cdot
s_{C}(Y_{i})\leq s(C)+1-s(C)=1.$

The first inequality is because by Definition 3.8 it holds that $X_{i}$ is
allowed in $C$. The second inequality is by (16). The third inequality is by
Lemma 1.2; also, the conditions of Lemma 1.2 are indeed satisfied by Claim
F.1. Using similar arguments, we can show the claim for $i>t$ or $i>r$ by the
definition of $Z$.

  3. 3.

For all $i\in[p]$ and $G\in{\mathcal{G}}$ it holds that $|G\cap Z_{i}|\leq
k(G)$. If $|G\cap D_{C}|=0$ then the claim is trivially satisfied because
$X_{i}$ is allowed in the configuration $C$. Otherwise, if $i\leq t$ and
$i\leq r$:

$\displaystyle|G\cap Z_{i}|\leq{}$ $\displaystyle|G\cap X_{i}|+|G\cap
Y_{i}|\leq|G\cap C|+|G\cap Y_{i}|\leq|G\cap C|+k_{C}(G\cap D_{C})$
$\displaystyle\leq{}$ $\displaystyle|G\cap C|+\left(k(G)-|G\cap
C|\right)=k(C).$

The second inequality is because by Definition 3.8 it holds that $X_{i}$ is
allowed in $C$. The third inequality is by Lemma 1.2; also, the conditions of
Lemma 1.2 are indeed satisfied by Claim F.1. The fourth inequality is by (16).
Using similar arguments, we can show the claim for $i>t$ or $i>r$ by the
definition of $Z$.

  4. 4.

It holds that $p\leq(1+2{\varepsilon})\cdot|B_{C}|+2$.

$\displaystyle p={}$
$\displaystyle\max\\{r,t\\}\leq\max\left\\{|B_{C}|,(1+2{\varepsilon})\cdot\max\left\\{s_{C}(D_{C}),\max_{G\in{\mathcal{G}}_{C}}\frac{|G|}{k_{C}(G)}\right\\}+2\right\\}$
$\displaystyle\leq{}$
$\displaystyle\max\left\\{|B_{C}|,(1+2{\varepsilon})\cdot\max\left\\{\frac{s(D_{C})}{1-s(C)},\max_{G\in{\mathcal{G}}\text{
s.t. }G\cap D_{C}\neq\emptyset}\frac{|G\cap D_{C}|}{k(G)-|G\cap
C|}\right\\}+2\right\\}$ $\displaystyle\leq{}$
$\displaystyle\max\left\\{|B_{C}|,(1+2{\varepsilon})\cdot\max\left\\{\frac{(1-s(C))\cdot|B_{C}|}{1-s(C)},\max_{G\in{\mathcal{G}}\text{
s.t. }G\cap D_{C}\neq\emptyset}\frac{|B_{C}|\cdot(k(G)-|C\cap G|)}{k(G)-|G\cap
C|}\right\\}+2\right\\}$ $\displaystyle={}$
$\displaystyle(1+2{\varepsilon})\cdot|B_{C}|+2.$

The first inequality is by Lemma 1.2; also, the conditions of Lemma 1.2 are
indeed satisfied by Claim F.1. The second inequality is by (16). The third
inequality is by Definition 3.8.

∎

Proof of Lemma 3.10: For all $C\in\mathcal{H}$ let
$X^{C}=\textsf{tuple}(B_{C}),Y^{C}=\textsf{Greedy}({\mathcal{I}}_{C},{\varepsilon})$,
$X^{C}=(X^{C}_{1},\ldots,X^{C}_{r(C)})$,
$Y^{C}=(Y^{C}_{1},\ldots,Y^{C}_{t(C)})$, $S^{C}=D_{C}\cup\bigcup_{B\in
B_{C}}B$, $Z^{C}=X^{C}+Y^{C}$, and $P_{C}=(Z^{C}_{1},\ldots,Z^{C}_{p(C)})$. In
addition, let $P=(P_{1},\ldots,P_{a})$ be the tuple returned by Algorithm 5.
We prove the following.

  1. 1.

$P$ is a partition of $I$: Let $\ell\in I$. Then, by Definition 3.8 there is
exactly one $C\in\mathcal{H}$ such that $\ell\in S^{C}$; then, by Lemma 7.1
there is exactly one $i\in[p(C)]$ such that $\ell\in Z^{C}_{i}$; therefore, by
Step 5 of Algorithm 5 there is exactly one $j\in[a]$ such that $\ell\in P_{j}$
and the claim follows.

  2. 2.

For all $i\in[a]$ it holds that $s(P_{i})\leq 1$: By Step 5 of Algorithm 5
there is $C\in\mathcal{H}$ and $j\in[p(C)]$ such that $P_{j}=Z^{C}_{j}$.
Therefore, $s(P_{i})=s(Z^{C}_{j})\leq 1$ by Lemma 7.1.

  3. 3.

For all $i\in[a]$ and $G\in{\mathcal{G}}$ it holds that $|G\cap P_{i}|\leq
k(G)$: By Step 5 of Algorithm 5 there is $C\in\mathcal{H}$ and $j\in[p(C)]$
such that $P_{i}=Z^{C}_{j}$. Therefore, $|P_{i}\cap G|=|Z^{C}_{j}\cap G|\leq
k(G)$ by Lemma 7.1.

  4. 4.

The size of $P$ that is $a$ is at most $(1+2{\varepsilon})\cdot
m+2\cdot{\varepsilon}^{-22}\cdot Q^{2}({\varepsilon})$:

$a=\sum_{C\in\mathcal{H}}p(C)\leq\sum_{C\in\mathcal{H}}\left((1+2{\varepsilon})\cdot|B_{C}|+2\right)\leq(1+2{\varepsilon})\cdot
m+2\cdot{\varepsilon}^{-22}\cdot Q^{2}({\varepsilon})$

The first equality is by Step 5 of Algorithm 5. The first inequality is by
Lemma 7.1. The second inequality is because $\\{B_{C}\\}_{C\in\mathcal{H}}$ is
a partition of $\\{A_{i}~{}|~{}i\in[m]\\}$ and that
$|\mathcal{H}|\leq{\varepsilon}^{-22}\cdot Q^{2}({\varepsilon})$ by Definition
3.8.

∎

##  Appendix G Omitted Proofs of Section 8

In this section we refer to a BPP instance ${\mathcal{J}}$ fixed in Section 8
and a given parameter ${\varepsilon}\in(0,0.1]$; in addition, we use
${\mathcal{I}}=\textsf{Reduce}({\varepsilon},{\mathcal{J}})$ as in Section 8.

###  G.1 Proofs From the Reduction

######  Lemma G.1.

For every minimal pivot $w\in\\{2,\ldots,{\varepsilon}^{-1}+1\\}$ of
$\mathcal{J}$ it holds that
$s(I_{w})\leq{\varepsilon}\cdot\textnormal{OPT}(\mathcal{J})$.

###### Proof.

$s(I_{w})\leq{\varepsilon}\cdot
s\left(\bigcup_{i\in\\{2,\ldots,{\varepsilon}^{-1}+1\\}}I_{i}\right)\leq{\varepsilon}\cdot
s(I)\leq{\varepsilon}\cdot\textnormal{OPT}({\mathcal{J}}).$

The first inequality is because $I_{2},\ldots,I_{{\varepsilon}^{-1}+1}$ are
${\varepsilon}^{-1}$ disjoint subsets of items and by (18) it holds that
$I_{w}$ is an interval of minimum total size. The last inequality is because
each bin may contain total size at most $1$; thus, the total size of items is
a lower bound to the optimum.

∎

Proof of Lemma 8.1:

If $\textnormal{OPT}({\mathcal{J}})=0$ there are no items and the claim
trivially follows. Otherwise, let

${\mathcal{B}}=\big{\\{}G\in{\mathcal{G}}~{}\big{|}~{}|G\cap(H_{w}\cup
I_{w})|\geq{\varepsilon}^{2w+4}\big{\\}}$

be the subset of groups that contain at least ${\varepsilon}^{2w+4}$ $w$-heavy
and $w$-medium items. The following holds for all $G\in{\mathcal{B}}$:

$\displaystyle s(G)\geq{}$ $\displaystyle s\left(G\cap(H_{w}\cup
I_{w})\right)=\sum_{\ell\in G\cap(H_{w}\cup I_{w})}s(\ell)\geq\sum_{\ell\in
G\cap(H_{w}\cup
I_{w})}{\varepsilon}^{w+1}={\varepsilon}^{w+1}\cdot|G\cap(H_{w}\cup I_{w})|$
(93) $\displaystyle\geq{}$
$\displaystyle{\varepsilon}^{w+1}\cdot{\varepsilon}^{2w+4}\cdot\textnormal{OPT}({\mathcal{J}})={\varepsilon}^{3w+5}\cdot\textnormal{OPT}({\mathcal{J}}).$

The second inequality is because the size of a $w$-medium item is at least
${\varepsilon}^{w+1}$. The third inequality is because $G\in{\mathcal{B}}$.
Therefore,

$|{\mathcal{B}}|=\sum_{G\in{\mathcal{B}}}1\leq\sum_{G\in{\mathcal{B}}}\frac{s(G)}{{\varepsilon}^{3w+5}\cdot\textnormal{OPT}({\mathcal{J}})}\leq\frac{s(I)}{{\varepsilon}^{3w+5}\cdot\textnormal{OPT}({\mathcal{J}})}\leq\frac{\textnormal{OPT}({\mathcal{J}})}{{\varepsilon}^{3w+5}\cdot\textnormal{OPT}({\mathcal{J}})}={\varepsilon}^{-3w-5}.$

The first inequality is by (93). ∎

The next two lemmas combined are essentially the proof of Condition 1 in Lemma
2.2.

######  Lemma G.2.

For ${\mathcal{I}}=\textsf{Reduce}({\varepsilon},{\mathcal{J}})$ it holds that
$OPT(\mathcal{I})\leq OPT({\cal J})$.

###### Proof.

Let $A=(A_{1},\ldots,A_{m})$ be a packing of ${\mathcal{J}}$ and let
$w\in\\{2,\ldots,{\varepsilon}^{-1}+1\\}$ chosen in Step 6 of Algorithm 6. We
show that $A$ is also a packing of ${\mathcal{I}}$ which concludes the proof.
By the definition of packing, we prove the following.

  * •

It holds that $A$ is a partition of $I$. Follows because $A$ is a packing of
${\mathcal{J}}$ and because that by Step 6 the sets of items in
${\mathcal{I}},{\mathcal{J}}$ are identical.

  * •

For all $i\in[m]$ it holds that $s(A_{i})\leq 1$. By Step 6 the set of items
and the size functions in ${\mathcal{I}},{\mathcal{J}}$ are identical and the
proof follows.

  * •

For all $G\in{\mathcal{G}}_{R}$ and $i\in[m]$ it holds that $|G\cap A_{i}|\leq
k_{R}(G)$. We split into three cases by Step 5.

    1. 1.

$G\in{\mathcal{G}}_{L}(w)$. Then, $|G\cap A_{i}|\leq k(G)=k_{R}(G)$ where the
inequality is because $A$ is a packing of ${\mathcal{J}}$ and the equality is
by Step 5.

    2. 2.

$G=G^{\prime}\setminus H_{w}\text{ s.t.
}G^{\prime}\in{\mathcal{G}}\setminus{\mathcal{G}}_{L}(w)$. Then,

$|G\cap A_{i}|\leq|(G\cup(G^{\prime}\cap H_{w}))\cap A_{i}|=|G^{\prime}\cap
A_{i}|\leq k(G^{\prime})=k_{R}(G).$

The second inequality is because $A$ is a packing of ${\mathcal{J}}$. The last
equality is by Step 5.

    3. 3.

$G=\Gamma_{w}$. Then, $|G\cap A_{i}|=|\Gamma_{w}\cap
A_{i}|\leq|\Gamma_{w}|<|\Gamma_{w}+1|=k_{R}(\Gamma_{w})=k_{R}(G)$ where the
second equality is by Step 5.

∎

######  Lemma G.3.

${\mathcal{I}}$ is ${\varepsilon}$-structured.

###### Proof.

Let $w\in\\{2,\ldots,{\varepsilon}^{-1}+1\\}$ chosen in Step 6 of Algorithm 6.
Therefore,

$\displaystyle\big{|}\\{G{}$
$\displaystyle\in{\mathcal{G}}_{R}~{}|~{}\exists\ell\in G\text{ s.t.
}s(\ell)\geq{\varepsilon}^{2}\\}\big{|}\leq\big{|}\\{G\in{\mathcal{G}}_{R}~{}|~{}G\cap
H_{w}\neq\emptyset\\}\big{|}\leq|{\mathcal{G}}_{L}(w)|+|\\{\Gamma_{w}\\}|$
$\displaystyle\leq{}$
$\displaystyle{\varepsilon}^{-3w-5}+1\leq{\varepsilon}^{-3w-6}\leq{\varepsilon}^{-3{\varepsilon}^{-1}-3-6}\leq{\varepsilon}^{-4{\varepsilon}^{-1}}\leq{\varepsilon}^{-{\varepsilon}^{-2}}=K({\varepsilon}).$

The first inequality is because for all $\ell\in I\setminus H_{w}$ it holds
that $s(\ell)\leq{\varepsilon}^{2}$ because $w\geq 2$ by (18). ∎

###  G.2 Proofs From the Reconstruction

For the following, let $A=(A_{1},\ldots,A_{m})$ be a packing of
${\mathcal{I}}$ and let $F_{A}=(U_{1},\ldots,U_{m^{\prime}})$ (see (22)). In
addition, for all $w\in\\{2,\ldots,{\varepsilon}^{-1}+1\\}$ let
$Y_{w}=I\setminus(H_{w}\cup I_{w})$.

######  Claim G.4.

For all $i\in[m^{\prime}]$ and $G\in{\mathcal{G}}$ it holds that $|G\cap
Y_{w}\cap U_{i}|\leq k(G)$.

###### Proof.

If $i\in[m^{\prime}]\setminus[m]$, then by (22) it holds that $|G\cap
Y_{w}\cap U_{i}|=0\leq k(G)$. Otherwise, we split into two cases by Step 6 of
Algorithm 6.

  1. 1.

$G\in{\mathcal{G}}_{L}(w)$. Then,

$|G\cap Y_{w}\cap U_{i}|=|G\cap
Y_{w}\cap\left((A_{i}\setminus(\Gamma_{w}\cup\Omega_{w}))\cup
B_{i}\right)|\leq|G\cap Y_{w}\cap A_{i}|\leq|G\cap A_{i}|\leq k_{R}(G)=k(G).$

The first inequality is because $(\Omega_{w}\cup\Gamma_{w})\cap
Y_{w}=\emptyset$ by (20), (21), and because $B_{i}\subseteq\Gamma_{w}$ by
Lemma 8.2. The third inequality is because $A$ is a packing of
${\mathcal{I}}$. The last equality is by Step 5 of Algorithm 6.

  2. 2.

$G\in{\mathcal{G}}\setminus{\mathcal{G}}_{L}(w)$. Then, by (19) it holds that
$G\setminus H_{w}\in{\mathcal{G}}_{S}(w)$. Therefore,

$|G\cap Y_{w}\cap U_{i}|=|G\cap
Y_{w}\cap\left((A_{i}\setminus(\Gamma_{w}\cup\Omega_{w}))\cup
B_{i}\right)|\leq|G\cap Y_{w}\cap A_{i}|\leq|G\cap A_{i}|\leq k_{R}(G\setminus
H_{w})=k(G).$

The first inequality is because $B_{i}\subseteq\Gamma_{w}$ by Lemma 8.2. The
third inequality is because $A$ is a packing of ${\mathcal{I}}$. The last
equality is by Step 5 of Algorithm 6.

∎

######  Claim G.5.

For all $i\in[m^{\prime}]$ and $G\in{\mathcal{G}}$ it holds that
$|F_{A}(i,G)|\leq|G\cap U_{i}\cap H_{w}|$.

###### Proof.

We split into two cases by Step 6 of Algorithm 6.

  1. 1.

$G\in{\mathcal{G}}_{L}(w)$.

$\displaystyle|F_{A}(i,G)|=\max\\{|G\cap U_{i}|-k(G),0\\}\leq{}$
$\displaystyle\max\\{k_{R}(G)-k(G),0\\}=\max\\{k(G)-k(G),0\\}=0.$

The first equality is because for any bin $i\in[m^{\prime}]$ and group
$G\in{\mathcal{G}}$ it holds that $F_{A}(i,G)$ is an exclusion-minimal subset
of $w$-light items from $U_{i}$ such that $|(U_{i}\setminus F_{A}(i,G))\cap
G|\leq k(G)$. The first inequality is because $A$ is a packing of
${\mathcal{I}}$. The second equality is by Step 5 of Algorithm 6.

  2. 2.

$G\in{\mathcal{G}}\setminus{\mathcal{G}}_{L}(w)$. Then,

$\displaystyle|F_{A}(i,G)|={}$ $\displaystyle\max\\{|G\cap
U_{i}|-k(G),0\\}=\max\\{|G\cap U_{i}\cap H_{w}|+|G\cap U_{i}\cap
Y_{w}|-k(G),0\\}$ $\displaystyle\leq{}$ $\displaystyle\max\\{|G\cap U_{i}\cap
H_{w}|+k(G)-k(G),0\\}=|G\cap U_{i}\cap H_{w}|.$

The first equality is because for any bin $i\in[m^{\prime}]$ and group
$G\in{\mathcal{G}}$ it holds that $F_{A}(i,G)$ is an exclusion-minimal subset
of $w$-light items from $U_{i}$ such that $|(U_{i}\setminus F_{A}(i,G))\cap
G|\leq k(G)$. The second equality is because $\Omega_{w}\cap U_{i}=\emptyset$
by (21), (22), and because Fill(A) is a partition of items in $\Gamma_{w}$ by
Lemma 8.2. The inequality is by Claim G.4.

∎

######  Claim G.6.

For all $G\in{\mathcal{G}}$ it holds that $|D(A)\cap
G|\leq{\varepsilon}^{2w+4}\textnormal{OPT}({\mathcal{J}})$.

###### Proof.

We split into three cases by Step 5 of Algorithm 6.

  1. 1.

$G\in{\mathcal{G}}_{L}(w)$. Then, we use the following inequality.

$|G\cap U_{i}|=|G\cap\left((A_{i}\setminus(\Gamma_{w}\cup\Omega_{w}))\cup
B_{i}\right)|=|G\cap A_{i}|\leq k_{R}(G)=k(G).$ (94)

The second equality is because $(\Gamma_{w}\cup\Omega_{w})\cap G=\emptyset$ by
(20) and $B_{i}\subseteq\Gamma_{w}$ by Lemma 8.2. Therefore,

$|D(A)\cap
G|=\sum_{i\in[m^{\prime}]}|F_{A}(i,G)|=\sum_{i\in[m^{\prime}]}\max\left\\{|G\cap
U_{i}|-k(G),0\right\\}=0.$

The second equality is because for any bin $i\in[m^{\prime}]$ and group
$G\in{\mathcal{G}}$ it holds that $F_{A}(i,G)$ is an exclusion-minimal subset
of $w$-light items from $U_{i}$ such that $|(U_{i}\setminus F_{A}(i,G))\cap
G|\leq k(G)$. The last equality is by (94).

  2. 2.

$G\in{\mathcal{G}}\setminus{\mathcal{G}}_{L}(w)$. Now,

$\displaystyle|D(A)\cap G|={}$
$\displaystyle\left|\bigcup_{i\in[m^{\prime}]}F_{A}(i,G)\right|\leq\sum_{i\in[m^{\prime}]}|G\cap
U_{i}\cap H_{w}|=|G\cap
H_{w}|\leq{\varepsilon}^{2w+4}\textnormal{OPT}({\mathcal{J}}).$

The first inequality is by Claim G.5. The second equality is by (22) and
because $A$ is a packing of ${\mathcal{I}}$. The last inequality is by Lemma
8.1.

∎

######  Claim G.7.

For all $i\in[m^{\prime}]$ and $G\in{\mathcal{G}}$ it holds that
$s(F_{A}(i,G))\leq{\varepsilon}\cdot s(U_{i}\cap H_{w}\cap G)$.

###### Proof.

If $F_{A}(i,G)=\emptyset$ then the claim is trivially satisfied. Otherwise, by
Claim G.5 it holds that $U_{i}\cap H_{w}\cap G\neq\emptyset$. Therefore,

$\displaystyle s(F_{A}(i,G))={}$ $\displaystyle\sum_{\ell\in
F_{A}(i,G)}s(\ell)\leq\sum_{\ell\in F_{A}(i,G)}\max_{\ell\in
F_{A}(i,G)}s(\ell)=|F_{A}(i,G)|\cdot\max_{\ell\in
F_{A}(i,G)}s(\ell)\leq|U_{i}\cap H_{w}\cap G|\max_{\ell\in F_{A}(i,G)}s(\ell)$
$\displaystyle\leq{}$ $\displaystyle|U_{i}\cap H_{w}\cap
G|\cdot{\varepsilon}\cdot\min_{\ell\in U_{i}\cap H_{w}\cap
G}s(\ell)\leq{\varepsilon}\cdot\sum_{\ell\in U_{i}\cap H_{w}\cap
G}s(\ell)={\varepsilon}\cdot s(U_{i}\cap H_{w}\cap G).$

The second inequality is by Claim G.5. The third inequality is because the
size of the largest item in $Y_{w}$ is at least ${\varepsilon}^{-1}$ times
smaller compared to the smallest item in $H_{w}$ by (17).

∎

######  Lemma G.8.

$s(D(A))\leq{\varepsilon}\cdot\textnormal{OPT}({\mathcal{J}})$.

###### Proof.

$\displaystyle s(D(A))={}$
$\displaystyle\sum_{G\in{\mathcal{G}}}\sum_{i\in[m^{\prime}]}s(F_{A}(i,G))\leq\sum_{G\in{\mathcal{G}}}\sum_{i\in[m^{\prime}]}{\varepsilon}\cdot
s(U_{i}\cap H_{w}\cap
G)\leq{\varepsilon}\cdot\sum_{G\in{\mathcal{G}}}\sum_{i\in[m^{\prime}]}\cdot
s(U_{i}\cap G)$ $\displaystyle\leq{}$ $\displaystyle{\varepsilon}\cdot
s(I)\leq{\varepsilon}\cdot\textnormal{OPT}({\mathcal{J}}).$

The first equality is by (23). The first inequality is by Claim G.7. ∎

Proof of Lemma 8.3: The proof follows by Claim G.8 and Claim G.6.

######  Lemma G.9.

Given a packing $A$ for
$\mathcal{I}=\textsf{Reduce}({\varepsilon},\mathcal{J})$ of size $m$,
Algorithm 7 returns in time
$\textnormal{poly}(|{\mathcal{J}}|,\frac{1}{{\varepsilon}})$ a packing $F$ for
the instance ${\cal J}$ of size $\phi$ where
$\phi<m+13{\varepsilon}\cdot\textnormal{OPT}({\mathcal{J}})+1$.

###### Proof.

In the proof of the lemma we use several auxiliary claims. For simplicity, by
Step 7, let $F_{A}\setminus E=(Z_{1}\ldots Z_{m^{\prime}})$,
$\textsf{Greedy}(\mathcal{E})=(X_{1}\ldots X_{x})$, $F=\left(F_{A}\setminus
E\right)\oplus\textsf{Greedy}(\mathcal{E})$, and $F=(F_{1},\ldots,F_{\phi})$.
Also, for the following let
$(B_{1},\ldots,B_{m},R)=\textsf{Fill}(\mathcal{J},A)$. Finally, recall the
definition of $\mathcal{{\mathcal{I}}}$-partition from Section 8. For
$\beta={\varepsilon}^{-w-2}$, we define $P_{1},\ldots,P_{q}$ to be the
$\mathcal{{\mathcal{I}}}$-partition: a partition of $\Gamma_{w}$ by a non
decreasing order of item sizes such that for all $1\leq i\leq j<q$ and
$\ell\in P_{i},y\in P_{j}$ it holds that $s(\ell)\geq s(y)$,
$|P_{i}|={\left\lceil\frac{|\Gamma_{w}|}{\beta}\right\rceil}$, and $P_{q}$
contains the remaining items from $\Gamma_{w}$. It follows that $q\leq\beta$
and we define $q({\mathcal{I}})=q$.

######  Claim G.10.

$F$ is a packing of ${\mathcal{J}}$.

###### Proof.

We prove the necessary conditions of packing as follows.

  1. 1.

$F$ is a partition of $I$. Let $\ell\in I$. By the following three
complementary cases, we conclude that $F$ is a partition of $I$.

     * •

$\ell\in E$. Then, there is exactly one $j\in[x]$ such that $\ell\in X_{j}$ by
Lemma 1.2 and (24); hence, there is exactly one $i\in[\phi]$ such that
$\ell\in F_{i}$ because by Step 7 of Algorithm 7 for all $i\in[m^{\prime}]$ it
holds that $\ell\notin Z_{i}$.

     * •

$\ell\in\Gamma_{w}$. Then, there is exactly one $i\in[m]$ such that $\ell\in
A_{i}$ because $A$ is a packing of ${\mathcal{I}}$. Then, by Lemma 8.2 and by
(22) there is exactly one $i\in[m^{\prime}]$ such that $\ell\in Z_{i}$. Hence,
there is exactly one $i\in[\phi]$ such that $\ell\in F_{i}$ because by (24)
for all $j\in[x]$ it holds that $\ell\notin X_{j}$.

     * •

$\ell\in I\setminus(\Gamma_{w}\cup E)$. Then, there is exactly one $i\in[m]$
such that $\ell\in A_{i}$ because $A$ is a packing of ${\mathcal{I}}$. Then,
by (22) there is exactly one $i\in[m^{\prime}]$ such that $\ell\in Z_{i}$.
Hence, there is exactly one $i\in[\phi]$ such that $\ell\in F_{i}$ because by
(24) for all $j\in[x]$ it holds that $\ell\notin X_{j}$.

  2. 2.

Let $i\in[\phi]$. By Step 7 of Algorithm 7 it holds that $F_{i}=Z_{i}$ or
$F_{i}=X_{j}$ for $j=i-m^{\prime}$. We split into two cases based on the
latter distinction.

     * •

$F_{i}=Z_{i}$. Then, by (22) if $U_{i}=\\{\ell\\}$ for $\ell\in R$ it holds
that $s(F_{i})=s(Z_{i})=s(\ell)\leq 1$ because the sizes of items are bounded
by $1$. Otherwise, by (22) it holds that
$Z_{i}=((A_{i}\setminus(\Gamma_{w}\cup\Omega_{w}))\cup B_{i})\setminus E$.
Therefore, we use the following inequalities.

$\displaystyle s(B_{i})={}$
$\displaystyle\sum_{j\in\\{2,\ldots,q({\mathcal{I}})\\}~{}}\sum_{\ell\in
B_{i}\cap
P_{j}}s(\ell)\leq\sum_{j\in\\{2,\ldots,q({\mathcal{I}})\\}~{}}\sum_{\ell\in
B_{i}\cap P_{j}}\max_{\ell\in P_{j}}s(\ell)$ (95) $\displaystyle\leq{}$
$\displaystyle\sum_{j\in\\{2,\ldots,q({\mathcal{I}})\\}~{}}|B_{i}\cap
P_{j}|\cdot\max_{\ell\in P_{j}}s(\ell).$

The first equality is because $B_{i}\cap P_{1}=\emptyset$ by Lemma 8.2. In
addition,

$\displaystyle\sum_{j\in\\{2,\ldots,q({\mathcal{I}})\\}~{}}{}$
$\displaystyle|B_{i}\cap P_{j}|\cdot\max_{\ell\in
P_{j}}s(\ell)\leq\sum_{j\in\\{2,\ldots,q({\mathcal{I}})\\}~{}}|A_{i}\cap
P_{j-1}|\cdot\max_{\ell\in P_{j}}s(\ell)$ (96) $\displaystyle\leq{}$
$\displaystyle\sum_{j\in\\{2,\ldots,q({\mathcal{I}})\\}~{}}|A_{i}\cap
P_{j-1}|\cdot\min_{\ell\in P_{j-1}}s(\ell)$ $\displaystyle\leq{}$
$\displaystyle\sum_{j\in\\{2,\ldots,q({\mathcal{I}})\\}~{}}\sum_{\ell\in
A_{i}\cap P_{j-1}}s(\ell)\leq s(A_{i}\cap\Gamma_{w}).$

The first inequality is by Lemma 8.2. The third inequality is because for all
$j\in[q({\mathcal{I}})-1]$, $\ell\in P_{j},y\in P_{j+1}$ it holds that
$s(\ell)\geq s(y)$ by the definition of the ${\mathcal{I}}$-partition. Then,

$\displaystyle s(F_{i})={}$ $\displaystyle
s(U_{i})=s\big{(}((A_{i}\setminus(\Gamma_{w}\cup\Omega_{w}))\cup
B_{i})\setminus E\big{)}$ $\displaystyle\leq{}$ $\displaystyle
s\big{(}(A_{i}\setminus(\Gamma_{w}\cup\Omega_{w})\cup B_{i})\big{)}$
$\displaystyle={}$ $\displaystyle
s(A_{i}\setminus(\Gamma_{w}\cup\Omega_{w}))+s(B_{i})$ $\displaystyle\leq{}$
$\displaystyle
s(A_{i}\setminus(\Gamma_{w}\cup\Omega_{w}))+s(A_{i}\cap\Gamma_{w})\leq
s(A_{i})\leq 1.$

The second inequality is by (95) and (96). The last inequality is since $A$ is
a packing of ${\mathcal{I}}$.

     * •

$F_{i}=X_{j}$ for $j=i-m^{\prime}$. Then, It holds that $s(F_{i})\leq 1$ by
Lemma 1.2.

  3. 3.

Let $G\in{\mathcal{G}}$ and $i\in[\phi]$. We split into two cases by Step 7.

     * •

$F_{i}=X_{j}$ for $j=i-m^{\prime}$. Then,

$|F_{i}\cap G|=|X_{j}\cap G|=|X_{j}\cap E\cap G|\leq k_{E}(G\cap E)=k(G).$

The second and the last equalities are by (24). The inequality is by Lemma
1.2.

     * •

$F_{i}=Z_{i}$. Then, we split into two complementary cases. If
$G\in{\mathcal{G}}_{L}(w)$:

$\displaystyle|F_{i}\cap G|=|Z_{i}\cap
G|=|((A_{i}\setminus(\Gamma_{w}\cup\Omega_{w}))\cup B_{i})\cap G|=|A_{i}\cap
G|\leq k_{R}(G)=k(G).$

The second equality is by (22). The third equality is because
$G\in{\mathcal{G}}_{L}(w)$; hence, $G\cap\Gamma_{w}=\emptyset$ and $G\cap
B_{i}\cap\Omega_{w}=\emptyset$ by (20) and (21), respectively. The inequality
is because $A$ is a packing of ${\mathcal{I}}$. The last equality is by Step 5
of Algorithm 6. Otherwise, $G\in{\mathcal{G}}\setminus{\mathcal{G}}_{L}(w)$.
Then,

$\displaystyle|F_{i}\cap G|\leq{}$ $\displaystyle|F_{i}\cap G\cap
H_{w}|+|F_{i}\cap G\cap Y_{w}|$ (97) $\displaystyle\leq{}$
$\displaystyle|F_{i}\cap G\cap H_{w}|+\max\\{0,k(G)-|F_{i}\cap G\cap
H_{w}|\\}$ $\displaystyle={}$ $\displaystyle\max\\{|F_{i}\cap G\cap
H_{w}|,k(G)\\}\leq\max\\{|B_{i}\cap G|,k(G)\\}\leq k(G).$

The first equality is because $\Omega_{w}\cap G\cap U_{i}=\emptyset$ by (22)
since $G\in{\mathcal{G}}\setminus{\mathcal{G}}_{L}(w)$. The second inequality
is by (23): we discard to $F_{A}(i,G)$ only $w$-light items until reaching at
most $k(G)$ items in $U_{i}$. The last equality is by (22) and because
$G\in{\mathcal{G}}\setminus{\mathcal{G}}_{L}(w)$. The last inequality is by
Lemma 8.2.

∎

######  Claim G.11.

$s(E)\leq 2{\varepsilon}\cdot\textnormal{OPT}({\mathcal{J}})$.

###### Proof.

$\displaystyle s(E)\leq{}$ $\displaystyle s(I_{w})+s(D(A))\leq
2{\varepsilon}\cdot\textnormal{OPT}({\mathcal{J}}).$

The first inequality is by (24). The second inequality is by Lemma G.1 and
Lemma 8.3.

∎

######  Claim G.12.

For all $G\in{\mathcal{G}}$ it holds that $|G\cap E|\leq
2{\varepsilon}\cdot\textnormal{OPT}({\mathcal{J}})$.

###### Proof.

We split into two cases.

  1. 1.

$G\in{\mathcal{G}}_{L}(w)$. Then,

$\displaystyle|G\cap E|={}$ $\displaystyle|G\cap
D(A)|=\left|\bigcup_{i\in[m^{\prime}]}F_{A}(i,G)\right|=\sum_{i\in[m^{\prime}]}\max\\{|G\cap
U_{i}|-k(G),0\\}$ $\displaystyle\leq{}$
$\displaystyle\sum_{i\in[m^{\prime}]}\max\\{k_{R}(G)-k(G),0\\}=\sum_{i\in[m^{\prime}]}\max\\{k(G)-k(G),0\\}=0.$

The first equality is by (24). The first inequality is because $A$ is a
packing of ${\mathcal{I}}$ and by (22). The fourth equality is by Step 5 of
Algorithm 6.

  2. 2.

$G\in{\mathcal{G}}\setminus{\mathcal{G}}_{L}(w)$. We use the following
inequality.

$|G\cap E\cap Y_{w}|=|G\cap
D(A)|\leq{\varepsilon}\cdot\textnormal{OPT}({\mathcal{J}}).$ (98)

The equality is by (23) and (24). The inequality is by Lemma 8.3. Therefore,

$|G\cap E|=|G\cap E\cap Y_{w}|+|G\cap E\cap(H_{w}\cup I_{w})|\leq
2{\varepsilon}\cdot\textnormal{OPT}({\mathcal{J}}).$

The inequality is by Lemma 8.1 and by (98).

∎

######  Claim G.13.

$V(\mathcal{E})\leq 2{\varepsilon}\cdot\textnormal{OPT}({\mathcal{J}})$.

###### Proof.

$V(\mathcal{E})=\max_{G\in{\mathcal{G}}_{E}}{\left\lceil\frac{|G|}{|k_{E}(G)|}\right\rceil}\leq\max_{G\in{\mathcal{G}}_{E}}|G|=\max_{G\in{\mathcal{G}}}|G\cap
E|\leq 2{\varepsilon}\cdot\textnormal{OPT}({\mathcal{J}}).$

The first inequality is because for all $G\in{\mathcal{G}}_{E}$ it holds that
$k_{E}(G)\geq 1$. The second equality is by (24). The last inequality is by
Claim G.12.

∎

######  Claim G.14.

$\phi<m+13{\varepsilon}\cdot\textnormal{OPT}({\mathcal{J}})+1$

###### Proof.

$\displaystyle\phi={}$ $\displaystyle m^{\prime}+x\leq m+|R|+x\leq
m+{\varepsilon}\cdot\textnormal{OPT}({\mathcal{J}})+1+(1+2)\cdot\max\\{2s(E),s(E)+V(\mathcal{E})\\}$
$\displaystyle\leq{}$ $\displaystyle
m+13{\varepsilon}\cdot\textnormal{OPT}({\mathcal{J}})+1.$

The first equality is by Step 7 of Algorithm 7. The first inequality is by
(22). The second inequality is by Lemma 8.2 and by Lemma 1.2. The last
inequality is by Claim G.11 and Claim G.13. ∎

######  Claim G.15.

The running time of Algorithm 7 is
$\textnormal{poly}(|{\mathcal{J}}|,\frac{1}{{\varepsilon}})$.

###### Proof.

By Lemma 8.2, Step 7 can be computed in time
$\textnormal{poly}(|{\mathcal{J}}|,\frac{1}{{\varepsilon}})$. By (24), the
discarded instance in Step 7 can be computed in time
$\textnormal{poly}(|{\mathcal{J}}|,\frac{1}{{\varepsilon}})$. By Lemma 1.2,
Step 7 can be computed in time
$\textnormal{poly}(|{\mathcal{J}}|,\frac{1}{{\varepsilon}})$; also,
concatenating two tuples takes linear time in the size of the instance. The
overall running time is therefore
$\textnormal{poly}(|{\mathcal{J}}|,\frac{1}{{\varepsilon}})$. ∎

The proof of Lemma G.9 follows by Claim G.10, Claim G.14, and Claim G.15. ∎

Proof of Lemma 2.2:

Condition 1 holds By Lemma G.2 and Lemma G.3. Condition 2 holds By Lemma G.9.
∎

###  G.3 Algorithm Fill

In this section we prove Lemma 8.2. Recall the definition of
$\mathcal{{\mathcal{I}}}$-partition from Section 8. For
$\beta={\varepsilon}^{-w-2}$, we define $P_{1},\ldots,P_{q}$ to be the
$\mathcal{{\mathcal{I}}}$-partition: a partition of $\Gamma_{w}$ by a non
decreasing order of item sizes such that for all $1\leq i\leq j<q$ and
$\ell\in P_{i},y\in P_{j}$ it holds that $s(\ell)\geq s(y)$,
$|P_{i}|={\left\lceil\frac{|\Gamma_{w}|}{\beta}\right\rceil}$, and $P_{q}$
contains the remaining items from $\Gamma_{w}$. It follows that $q\leq\beta$
and we define $q({\mathcal{I}})=q$. In Algorithm Fill we start with
$B_{1},\ldots,B_{m}$ empty sets and with $R=\Gamma_{w}$. In each iteration, we
try to move an item from $R$ to some $B_{i},i\in[m]$ if it is possible to do
so without violating one of the conditions of the lemma. When the above cannot
be done anymore, we return $(B_{1},\ldots,B_{m},R)$. The pseudocode of
Algorithm Fill is given in Algorithm 9. For the proof, we use the following
claims. Let $(B_{1},\ldots,B_{m},R)=\textsf{Fill}({\mathcal{J}},A)$.

1

2Initialize $R\leftarrow\Gamma_{w}$, $B_{i}\leftarrow\emptyset~{}:~{}\forall
i\in[m]$.

3while  _$\exists i\in[m],j\in\\{2,\ldots,q({\mathcal{I}})\\},\ell\in R\cap
P_{j}\textnormal{ s.t. }|B_{i}\cap P_{j}| <|A_{i}\cap
P_{j-1}|~{}\textnormal{and}~{}|\textnormal{{group}}(\ell)\cap B_{i}|<k(G)$ _
do

4

5 $B_{i}\leftarrow B_{i}\cup\\{\ell\\}$.

6 $R\leftarrow R\setminus\\{\ell\\}$.

7 end while

8

Return $(B_{1},\ldots,B_{m},R)$.

Algorithm 9 $\textsf{Fill}(\mathcal{J},A=(A_{1},\ldots,A_{m}))$

######  Claim G.16.

The running time of Algorithm 9 is
$\textnormal{poly}(|{\mathcal{J}}|,\frac{1}{{\varepsilon}})$.

###### Proof.

By Step 9, Step 9, and Step 9, each iteration of the while loop of the
algorithm takes linear time by trying at most all items. In addition, there
are $\textnormal{poly}(|{\mathcal{J}}|,\frac{1}{{\varepsilon}})$ iterations of
the while loop because by Step 9, Step 9, and Step 9 in each iteration an item
is moved from $R$ to some $B_{i},i\in[m]$ and never moved again. Therefore,
there are at most
$|I|=\textnormal{poly}(|{\mathcal{J}}|,\frac{1}{{\varepsilon}})$ iterations
and the claim follows.

∎

######  Claim G.17.

For each $k\in\mathbb{N}$, after $k$ iteration of Step 9 the following hold.

  1. 1.

$(B_{1},\ldots,B_{m},R)$ is a partition of $\Gamma_{w}$.

  2. 2.

For all $i\in[m]$ and $j\in\\{2,\ldots,q({\mathcal{I}})\\}$ it holds that
$|B_{i}\cap P_{j}|\leq|A_{i}\cap P_{j-1}|$ and $|B_{i}\cap P_{1}|=0$.

  3. 3.

For all $i\in[m]$ and $G\in{\mathcal{G}}$ it holds that $|B_{i}|\leq k(G)$.

###### Proof.

We prove the claim by induction on $k$. For the base case, let $k=0$.
Therefore,

  1. 1.

By Step 9 it holds that
$(B_{1},\ldots,B_{m},R)=(\emptyset,\ldots,\emptyset,\Gamma_{w})$, which is a
partition of $\Gamma_{w}$.

  2. 2.

By Step 9, for all $i\in[m]$ and $j\in\\{2,\ldots,q({\mathcal{I}})\\}$ it
holds that $|B_{i}\cap P_{j}|=|\emptyset\cap P_{j}|=0\leq|A_{i}\cap P_{j-1}|$
and $|B_{i}\cap P_{1}|=0$.

  3. 3.

By Step 9, for all $i\in[m]$ and $G\in{\mathcal{G}}$ it holds that
$|B_{i}|=|\emptyset|=0\leq 1\leq k(G)$.

Assume that the claim holds for some $k\in\mathbb{N}$. Now, for the step of
the induction observe $k+1$. Let $(B^{k}_{1},\ldots,B^{k}_{m},R^{k})$,
$(B^{k+1}_{1},\ldots,B^{k+1}_{m},R^{k+1})$ be the object
$(B_{1},\ldots,B_{m},R)$ before and after iteration $k+1$, respectively. Let
$i\in[m],j\in\\{2,\ldots,q({\mathcal{I}})\\}$ and $\ell\in P_{j}$ such that
$\ell$ is moved from $R^{k}$ to $B^{k+1}_{i}$ in iteration $k+1$ by Step 9 and
Step 9.

  1. 1.

By the assumption of the induction, it holds that
$(B^{k}_{1},\ldots,B^{k}_{m},R^{k})$ is a partition of $\Gamma_{w}$. Let
$y\in\Gamma_{w}$. If $y=\ell$, then $y\in B^{k+1}_{i}$ and do not belong to
any other set in the partition by Step 9 and Step 9. Otherwise, $y\neq\ell$;
then, there is exactly one set in $(B^{k}_{1},\ldots,B^{k}_{m},R^{k})$ to
which $y$ belongs by the assumption of the induction; also, in iteration
$k+1$, by Step 9 and Step 9 it holds that $y$ remains in the same set since
only $\ell$ is relocated in this iteration.

  2. 2.

Let $i^{\prime}\in[m]$ and $j^{\prime}\in\\{2,\ldots,q({\mathcal{I}})\\}$. If
$i^{\prime}=i$ and $j^{\prime}=j$, then

$|B^{k+1}_{i}\cap P_{j}|=|\\{\ell\\}|+|B^{k}_{i}\cap P_{j-1}|\leq|A_{i}\cap
P_{j-1}|.$

The equality is by Step 9 and Step 9. The inequality is by Step 9. Otherwise,
it holds that $i^{\prime}\neq i$ or $j^{\prime}\neq j$. Therefore,

$|B^{k+1}_{i}\cap P_{j}|=|B^{k}_{i}\cap P_{j-1}|\leq|A_{i}\cap P_{j-1}|.$

The equality is by Step 9 and Step 9. The inequality is by the assumption of
the induction.

  3. 3.

Let $i^{\prime}\in[m]$ and $G\in{\mathcal{G}}$. If $i^{\prime}=i$ and
$G=\textsf{group}(\ell)$, then

$|B^{k+1}_{i}\cap G|=|\ell\cap G|+|B^{k}_{i}\cap G|\leq k(G).$

The equality is by Step 9 and Step 9. The inequality is by Step 9. Otherwise,
it holds that $i^{\prime}\neq i$ or $G\neq\textsf{group}(\ell)$. Therefore,

$|B^{k+1}_{i}\cap G|=|B^{k}_{i}\cap G|\leq k(G).$

The equality is by Step 9 and Step 9. The inequality is by the assumption of
the induction.

∎

######  Claim G.18.

$|R\setminus
P_{q({\mathcal{I}})}|\leq{\varepsilon}^{2}\cdot\textnormal{OPT}({\mathcal{J}})$.

###### Proof.

Let $j\in\\{2,\ldots,q({\mathcal{I}})\\}$, and let $\ell\in R\cap P_{j}$ at
the end of Algorithm 9; in addition, let $G=\textsf{group}(\ell)$. Therefore,
by Step 9 at least one of the following holds for all $i\in[m]$.

  * •

(i) $|B_{i}\cap P_{j}|=|A_{i}\cap P_{j-1}|$.

  * •

(ii) $|G\cap B_{i}|=k(G)$.

Now, define the set of indices in $[m]$ in which the second condition defined
above holds.

$T=\\{i\in[m]~{}|~{}|G\cap B_{i}|=k(G)\\}.$ (99)

We use the following inequality

$\displaystyle|P_{j-1}|={}$ $\displaystyle\sum_{i\in[m]}|P_{j-1}\cap
A_{i}|=\sum_{i\in[m]\setminus T}|P_{j-1}\cap A_{i}|+\sum_{i\in T}|P_{j-1}\cap
A_{i}|=\sum_{i\in[m]\setminus T}|P_{j}\cap B_{i}|+\sum_{i\in T}|P_{j-1}\cap
A_{i}|$ (100) $\displaystyle\leq{}$ $\displaystyle\sum_{i\in[m]}|P_{j}\cap
B_{i}|+{\varepsilon}^{-w}\cdot|T|\leq\sum_{i\in[m]}|P_{j}\cap
B_{i}|+{\varepsilon}^{-w}\cdot{\varepsilon}^{2w+4}\cdot\textnormal{OPT}({\mathcal{J}})$
$\displaystyle={}$ $\displaystyle\sum_{i\in[m]}|P_{j}\cap
B_{i}|+{\varepsilon}^{w+4}\cdot\textnormal{OPT}({\mathcal{J}}).$

The first equality is because $A$ is a packing of $P_{j}$ in particular. The
third equality is by (99) and by (i). The first inequality is because
$\Gamma_{w}\subseteq H_{w}$; hence, the sizes of all items are at least
${\varepsilon}^{w}$ and there can be at most ${\varepsilon}^{-w}$ items from
$\Gamma_{w}$ in $A_{i},\forall i\in[m]$ because $A$ is a packing. The second
inequality is because for each $i\in T$ it holds that $G\cap
B_{i}\neq\emptyset$ by (99); thus, there are at least $|T|$ $w$-heavy items in
$G$ because $B_{i}\subseteq\Gamma_{w}$. Therefore, we get by Lemma 8.1 that
$|T|\leq{\varepsilon}^{2w+4}\cdot\textnormal{OPT}({\mathcal{J}})$ since each
$w$-small group contains at most
${\varepsilon}^{2w+4}\cdot\textnormal{OPT}({\mathcal{J}})$ $w$-heavy items in
particular.

Therefore, using the above for any $j\in\\{2,\ldots,q({\mathcal{I}})\\}$:

$\displaystyle|R\setminus P_{q({\mathcal{I}})}|={}$
$\displaystyle\sum_{j\in\\{2,\ldots,q({\mathcal{I}})\\}}|P_{j-1}|-\sum_{j\in\\{2,\ldots,q({\mathcal{I}})-1\\}}\sum_{i\in[m]}|P_{j}\cap
B_{i}|\leq{\varepsilon}^{w+4}\cdot\textnormal{OPT}({\mathcal{J}})\cdot
q({\mathcal{I}})$ $\displaystyle\leq{}$
$\displaystyle{\varepsilon}^{w+4}\cdot\textnormal{OPT}({\mathcal{J}})\cdot{\varepsilon}^{-w-2}={\varepsilon}^{2}\cdot\textnormal{OPT}({\mathcal{J}})$

The first equality is because $(B_{1},\ldots,B_{m},R)$ is a partition of
$\Gamma_{w}$ by Claim G.17. The first inequality is by (100). ∎

######  Claim G.19.

$|R|\leq{\varepsilon}\cdot\textnormal{OPT}({\mathcal{J}})+1$.

###### Proof.

We use the following inequality.

$\displaystyle|R\cap P_{q({\mathcal{I}})}|\leq{}$
$\displaystyle|P_{q({\mathcal{I}})}|\leq{\left\lceil\beta^{-1}\cdot|\Gamma_{w}|\right\rceil}\leq\beta^{-1}\cdot|\Gamma_{w}|+1={\varepsilon}^{w+2}\cdot|\Gamma_{w}|+1$
(101) $\displaystyle\leq{}$
$\displaystyle{\varepsilon}^{w+2}\cdot{\varepsilon}^{-w}\cdot\textnormal{OPT}({\mathcal{J}})+1={\varepsilon}^{2}\cdot\textnormal{OPT}({\mathcal{J}})+1.$

The second inequality is by the definition of ${\mathcal{I}}$-partition. The
fourth inequality is because $\Gamma_{w}\subseteq H_{w}$ by (20); hence, in
each bin in a packing of ${\mathcal{J}}$ there can be at most
${\varepsilon}^{-w}$ items from $\Gamma_{w}$ since each item is $w$-heavy and
has a size at least ${\varepsilon}^{-w}$; it follows that
$|\Gamma_{w}|\leq{\varepsilon}^{-w}\cdot\textnormal{OPT}({\mathcal{J}})$. Now,

$|R|=|R\cap P_{q({\mathcal{I}})}|+|R\setminus
P_{q({\mathcal{I}})}|\leq|P_{q({\mathcal{I}})}|+|R\setminus
P_{q({\mathcal{I}})}|\leq{\varepsilon}^{2}\cdot\textnormal{OPT}({\mathcal{J}})+1+2{\varepsilon}^{2}\cdot\textnormal{OPT}({\mathcal{J}})\leq{\varepsilon}\cdot\textnormal{OPT}({\mathcal{J}})+1.$

The second inequality is by (101) and by Claim G.18. ∎

Proof of Lemma 8.2: By Claim G.17 and Claim G.19 the output of the algorithm
satisfies the required properties, since by Step 9 the returned value is the
direct outcome of the while loop. In addition, the running time satisfies the
properties by Claim G.16.

##  Appendix H Algorithm Greedy

In this section we give the proof of Lemma 1.2. Algorithm Greedy is indeed a
greedy algorithm, which sequentially adds a new bin and tries to (i) maximize
the total size packed in the bin while (ii) packing items from groups which
have more items w.r.t. the matroid constraint. Some of the proofs from this
section are deferred to Section I.

For this section, fix a BPP instance ${\mathcal{I}}=(I,{\mathcal{G}},s,k)$ and
let $\delta\in(0,0.5)$ such that for all $\ell\in I$ it holds that
$s(\ell)\leq\delta$. We use ${\mathcal{C}}({\mathcal{J}})$ to denote the set
of configurations of a BPP instance ${\mathcal{J}}$. Also, recall that the
operator $\oplus$ denotes tuple (or, packing) concatenation. In addition, for
any $S\subseteq I$ we define ${\mathcal{I}}\setminus
S=(I_{S},{\mathcal{G}}_{S},s_{S},k_{S})$ as the BPP instance such that

$\displaystyle I_{S}=I\setminus
S,~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}\mathcal{G}_{S}=\\{G\cap
I_{S}\neq\emptyset~{}|~{}G\in{\mathcal{G}}\\},{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}$
(102) $\displaystyle s_{S}(\ell)=s(\ell),~{}~{}\forall\ell\in
I_{S},~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}k_{S}(G\cap I_{S})=k(G),~{}~{}\forall
G\in{\mathcal{G}}\text{ s.t. }G\cap I_{S}\neq\emptyset.{}{}{}{}{}{}{}{}{}{}{}$

######  Claim H.1.

For $S\in{\mathcal{C}}({\mathcal{I}})$ and a packing $X$ of
${\mathcal{I}}\setminus S$ it holds that $T=(S)\oplus X$ is a packing of
${\mathcal{I}}$.

Using Claim H.1, the algorithm first finds a configuration $S$ of
${\mathcal{I}}$ and then packs recursively the instance
${\mathcal{I}}\setminus A$. Recall that
$V(\mathcal{I})=\max_{G\in{\mathcal{G}}}{\left\lceil\frac{|G|}{|k(G)|}\right\rceil}$
and let the promise of ${\mathcal{I}}$ be a maximum bound over
$\textnormal{OPT}({\mathcal{I}})$ combining a bound over item sizes and over
the matroid:

$\displaystyle p({\mathcal{I}})=\max\left\\{(1+2\delta)\cdot
s(I)+2,V({\mathcal{I}})\right\\}.$ (103)

We show that the proposed algorithm Greedy constructs a packing of
${\mathcal{I}}$ in at most $p({\mathcal{I}})$ bins. For doing so, in each bin
we must pack enough items from groups $G\in{\mathcal{G}}$ which satisfy that
${\left\lceil\frac{|G|}{k(G)}\right\rceil}>p({\mathcal{I}})-1$; otherwise, the
packing might require more bins than $p({\mathcal{I}})$. Thus, we define the
set of bounding groups as

$\displaystyle{\mathcal{B}}({\mathcal{I}})=\left\\{G\in{\mathcal{G}}~{}\bigg{|}~{}{\left\lceil\frac{|G|}{k(G)}\right\rceil}>p({\mathcal{I}})-1\right\\}$
(104)

To guarantee that after packing the first bin by the algorithm we remain with
not too many items from some group, we must take certain number of items from
each bounding group. Specifically, for each bounding group
$G\in{\mathcal{B}}({\mathcal{I}})$ we define a bounding subset of $G$ as a
subset of items $S\subseteq G$ such that ${\left\lceil\frac{|G\setminus
S|}{k(G)}\right\rceil}\leq p({\mathcal{I}})-1$. Also, let $b(G)$ be the set of
all bounding subsets of $G$. Finally, define a minimal bounding subset of $G$
as a bounding subset $S^{*}\in b(G)$ of $G$ such that (i) $|S^{*}|\leq k(G)$
and (ii) $s(S^{*})\leq\frac{s(G)}{s(I)}$. For any
$G\in{\mathcal{B}}({\mathcal{I}})$ let $b^{*}(G)$ be the set of minimal
bounding subsets of $G$.

######  Lemma H.2.

For any $G\in{\mathcal{B}}({\mathcal{I}})$ it holds that
$b^{*}(G)\neq\emptyset$.

We generalize the definition of minimal bounding subset for the entire
instance. Specifically, define the set of bounding subsets of ${\mathcal{I}}$
as all unions of minimal bounding subsets of all bounding groups:

$b^{*}({\mathcal{I}})=\left\\{S\subseteq\bigcup_{G\in{\mathcal{B}}({\mathcal{I}})}G~{}\bigg{|}~{}\forall
G\in{\mathcal{B}}({\mathcal{I}})~{}:~{}S\cap G\in b^{*}(G)\right\\}$ (105)

######  Lemma H.3.

$b^{*}({\mathcal{I}})\neq\emptyset$.

###### Proof.

For all $G\in{\mathcal{B}}({\mathcal{I}})$ let $S_{G}\in b^{*}(G)$; there is
such $S_{G}\in b^{*}(G)$ by Lemma H.2. Now, define
$S=\bigcup_{G\in{\mathcal{B}}({\mathcal{I}})}S_{G}$; it follows by (105) that
$S\in b^{*}({\mathcal{I}})$. ∎

1

2if  _$I\in{\mathcal{C}}({\mathcal{I}})$_ then

3

4 return $(I)$.

5 end if

6

7Choose arbitrary $A\in b^{*}({\mathcal{I}})$ bounding subset of
${\mathcal{I}}$.

8while  _$s(A)\leq 1-\delta~{}\textnormal{and}~{}\exists\ell\in I\setminus
A\textnormal{ s.t. }|\textnormal{{group}}(\ell)\cap A|
<k\left(\textnormal{{group}}(\ell)\right)$ _ do

9

10 $A\leftarrow A\cup\\{\ell\\}$.

11 end while

12

13while  _$\exists\ell\in A,y\in I\setminus A\textnormal{ s.t. }s(y)
>s(\ell),\textnormal{{group}}(\ell)=\textnormal{{group}}(y),~{}\textnormal{and}~{}s(A)\leq
1-\delta$ _ do

14

15 $A\leftarrow\left(A\setminus\\{\ell\\}\right)\cup\\{y\\}$.

16 end while

17

18Return $(A)\oplus\textsf{Greedy}\left(\mathcal{I}\setminus A,\delta\right)$.

Algorithm 10 $\textsf{Greedy}(\mathcal{I}=(I,{\mathcal{G}},s,k),\delta)$

Given the definitions of bounding groups and bounding subsets, we describe
Algorithm Greedy. The algorithm is recursive. The base case is when the set of
items $I$ forms a configuration of ${\mathcal{I}}$; in this case, we simply
return a packing of one bin containing all items. Otherwise, we construct a
bounding subset $A$ of ${\mathcal{I}}$, which exists by Lemma H.3. Then, we
try to increase the total size of items in $A$, without exceeding the capacity
of the bin, in two ways. First, by adding items to $A$ from groups that do not
meet the cardinality constraint. Second, by replacing items from the same
group between $A$ and $I\setminus A$ such that the item moved into $A$ is of
larger size. Finally, we define the resulting bin $A$ as the first bin in the
packing, and pack recursively the instance ${\mathcal{I}}\setminus A$ using
Algorithm Greedy. We give the pseudocode of Algorithm Greedy in Algorithm 10.

The proof of Lemma 1.2 is based on viewing two complementary cases. First, if
$A$, the first bin in the packing, has small total size of items, namely
$s(A)<1-\delta$, then in this case $A$ is a basis of maximum total size of the
matroid over the items. This also holds for the following bins of the packing,
or we would be able to increase the size of $A$. Thus, an inductive argument
shows that the algorithm finds a packing of ${\mathcal{I}}$ in at most
$V({\mathcal{I}})$ bins.

The complementary case is where $s(A)\geq 1-\delta$; then, the total size
deducted from $s(I)$ by $A$ is significant, and there can be at most
$(1+2\delta)\cdot s(I)+1$ bins satisfying this property. In addition, it also
holds that $V({\mathcal{I}}\setminus A)\leq p({\mathcal{I}})-1$ because we
take a bounding subset for $A$ with additional items; using the first two
cases, it can be inductively deduced that the returned packing in case that
$s(A)\geq 1-\delta$ is of at most $p({\mathcal{I}})$ bins.

##  Appendix I Omitted Proofs of Section H

For this section as in Section H, we have a BPP instance
${\mathcal{I}}=(I,{\mathcal{G}},s,k)$ and $\delta\in(0,0.5)$ such that for all
$\ell\in I$ it holds that $s(\ell)\leq\delta$. Also, assume that
$I\neq\emptyset$ otherwise all proofs here are trivial.

Proof of Lemma H.1: We prove the claim by the definition of packing. For
convenience, let $T=(S,X_{1},\ldots,X_{m})$ and also
$T=(T_{1},\ldots,T_{m+1})$.

  1. 1.

It holds that $T$ is a partition of $I$. Let $\ell\in I$. If $\ell\in S$, then
$\ell\in T_{1}$ and for all $i\in[m+1]\setminus\\{1\\}$ it holds that
$\ell\notin T_{i}$ because $X_{i-1}\subseteq I\setminus S$. Otherwise, it
holds that $\ell\in I\setminus S$; therefore, because $X$ is a packing of
${\mathcal{I}}\setminus S$ there is exactly one $i\in[m]$ such that $\ell\in
X_{i}$ and it follows that $\ell\in T_{i+1}$ (only).

  2. 2.

For all $i\in[m+1]$ it holds that $s(T_{i})\leq 1$. If $i=1$ then
$s(T_{1})=s(S)\leq 1$ because $S\in{\mathcal{C}}({\mathcal{I}})$. Otherwise,
it holds that $s(T_{i})=s(X_{i-1})\leq 1$ because $X$ is a packing of
${\mathcal{I}}\setminus S$.

  3. 3.

For all $G\in{\mathcal{G}}$ and $i\in[m+1]$ it holds that $|T_{i}\cap G|\leq
k(G)$. If $i=1$ then $|T_{i}\cap G|=|G\cap S|\leq k(G)$ because
$S\in{\mathcal{C}}({\mathcal{I}})$. Otherwise, it holds that $|T_{i}\cap
G|=|X_{i-1}\cap G|\leq k_{S}(G\setminus S)=k(G)$. The inequality is because
$X$ is a packing of ${\mathcal{I}}\setminus S$. The last equality is by
(102).∎

Proof of Lemma H.2: Let $n=|G|$; by (103) and (104) it holds that $n\geq 1$.
Now, let $\ell_{1},\ldots,\ell_{n}$ be the items in $G$ in an increasing order
of item sizes. Define

$\psi=\operatorname*{arg\,min}_{\left\\{i\in[n]~{}\big{|}~{}{\left\lceil\frac{n-i}{k(G)}\right\rceil}\leq
V({\mathcal{I}})-1\right\\}}i.$ (106)

Observe that for $i=n$ it holds that
${\left\lceil\frac{n-i}{k(G)}\right\rceil}\leq V({\mathcal{I}})-1$ because
$n\geq 1$; thus, it follows that $\psi$ is well defined. Now, define
$S^{*}=\\{\ell_{1},\ldots,\ell_{\psi}\\}$. We show next that $S^{*}\in
b^{*}(G)$.

  * •

$S^{*}\in b(G)$. First, $S^{*}\subseteq G$ by definition. Second,

${\left\lceil\frac{|G\setminus
S^{*}|}{k(G)}\right\rceil}={\left\lceil\frac{n-\psi}{k(G)}\right\rceil}\leq
V({\mathcal{I}})-1\leq p({\mathcal{I}})-1.$

The first inequality is by (106). The last inequality is by (103).

  * •

$|S^{*}|\leq k(G)$.

$\displaystyle|S^{*}|={}$ $\displaystyle\psi\leq|G|-(V({\mathcal{I}})-1)\cdot
k(G)\leq|G|-\left(\frac{|G|}{k(G)}-1\right)\cdot k(G)=k(G).$ (107)

The first inequality is by (106), since $G\in{\mathcal{B}}({\mathcal{I}})$ and
${\left\lceil\frac{|G|-\left(|G|-(V({\mathcal{I}})-1)\cdot
k(G)\right)}{k(G)}\right\rceil}\leq(V({\mathcal{I}})-1)$ (recall that
$V({\mathcal{I}})\in\mathbb{N}$).

  * •

$s(S^{*})\leq\frac{s(G)}{s(I)}$. It holds that:

$s(S^{*})=\psi\cdot\frac{s(S^{*})}{\psi}\leq\psi\cdot\frac{s(G)}{n}\leq\frac{k(G)}{|G|}\cdot
s(G)\leq\frac{s(G)}{p({\mathcal{I}})-2}\leq\frac{s(G)}{(1+2\delta)\cdot
s(I)+2-2}\leq\frac{s(G)}{s(I)}.$

The first inequality is because $S^{*}$ is a subset of items of $G$ where each
item in $G\setminus S^{*}$ has a larger or equal size compared to the size of
any item in $S^{*}$ by the sorted order of the items; thus, the size of the
average item in $S^{*}$ is smaller or equal to the size of the average item in
$G$. The second inequality is by (107). The third inequality is by (104) and
that $G\in{\mathcal{B}}({\mathcal{I}})$: it holds that
$\frac{|G|}{k(G)}+1\geq{\left\lceil\frac{|G|}{k(G)}\right\rceil}>p({\mathcal{I}})-1$.
The fourth inequality is by (103).∎

Given a BPP instance ${\mathcal{J}}$, let $A^{{\mathcal{J}}}$ be the first
entry (from the left) of the returned tuple by
$\textsf{Greedy}({\mathcal{J}},\delta)$ and let
$A^{{\mathcal{J}}}_{0},A^{{\mathcal{J}}}_{1}$ be the object
$A^{{\mathcal{J}}}$ after Step 10 and after Step 10 in the computation of
$\textsf{Greedy}({\mathcal{J}},\delta)$, respectively. Note that
$A^{{\mathcal{J}}}_{0}$ is well defined (the algorithm is guaranteed to
construct $A^{{\mathcal{J}}}_{0}$) by Lemma H.3. For simplicity, we use
$A,A_{0},A_{1}$ instead of
$A^{{\mathcal{J}}},A^{{\mathcal{J}}}_{0},A^{{\mathcal{J}}}_{1}$, respectively,
when ${\mathcal{J}}={\mathcal{I}}$. Now, for the proof of Lemma 1.2, we use
the following auxiliary claims.

######  Claim I.1.

For any BPP instance ${\mathcal{I}}=(I,{\mathcal{G}},s,k)$ it holds that
$A_{0}\in{\mathcal{C}}({\mathcal{I}})$ and for each bounding group
$G\in{\mathcal{B}}({\mathcal{I}})$ it holds that
${\left\lceil\frac{|G\setminus A_{0}|}{k(G)}\right\rceil}\leq
p({\mathcal{I}})-1$.

###### Proof.

Observe that $A_{0}\in b^{*}({\mathcal{I}})$ by Step 10. In addition, note
that $A_{0}$ is well defined by Lemma H.3. Then, by (105) for each
$G\in{\mathcal{B}}({\mathcal{I}})$ there is $S_{G}\in b^{*}(G)$ such that
$A_{0}=\bigcup_{G\in{\mathcal{B}}({\mathcal{I}})}S_{G}$. We show the
conditions of the lemma as follows.

  * •

$s(A_{0})\leq 1$.

$s(A_{0})=s\left(\bigcup_{G\in{\mathcal{B}}({\mathcal{I}})}S_{G}\right)\leq\sum_{G\in{\mathcal{B}}({\mathcal{I}})}\frac{s(G)}{s(I)}\leq\frac{s(I)}{s(I)}=1.$

The first equality is by (105). The first inequality is by the definition of a
minimal bounding subset of a bounding group.

  * •

For all $G\in{\mathcal{G}}$ it holds that $|G\cap A_{0}|\leq k(G)$. If
$G\in{\mathcal{G}}\setminus{\mathcal{B}}({\mathcal{I}})$ then $|G\cap
A_{0}|=0<k(G)$ by (105). Otherwise, $|G\cap A_{0}|=\left|S_{G}\right|\leq