* •

Each pair $(q_{i},\ell_{i})$ is fitting.

We obtain the following proportionality claim.

######  Claim A.6.

Let $\kappa$ denote the number of disjoint fitting $ML/SL$ pairs in $I$. For
some positive constant $u$, suppose $\kappa\geq
u\cdot\mathrm{Opt}(\widetilde{I})$. Let $n_{1},n_{2}$ be two integers such
that $1\leq n_{1}\leq n_{2}\leq n$ and $n_{2}-n_{1}=\Theta(n)$. We have that
the number of fitting $ML/SL$ triplets in the sequence
$I_{\sigma}(n_{1}+1,n_{2})$ is at least

$\frac{u^{5}}{48(3-u)^{5}}\left(\frac{n_{2}-n_{1}}{n}\right)\kappa-o(\kappa)$

with high probability.

The proof of a general version of this claim is given in Section A.9. (This
version generalizes both 3.8 and A.6.)

We use the above claim with
$\kappa=\frac{r_{1}-17r_{1}\varepsilon}{2}\mathrm{Opt}(\widetilde{I}),u=\frac{r_{1}-17r_{1}\varepsilon}{2},n_{1}=n/4,n_{2}=n/2$.
Hence, we get that the number of disjoint fitting $ML/SL$ triplets in the time
segment $(t^{\prime}_{\sigma}+1,t_{\sigma})\supseteq(n/4,n/2)$ is at least

$\displaystyle\frac{1}{48}\left(\frac{\frac{r_{1}-17\varepsilon
r_{1}}{2}}{3-\frac{r_{1}-17\varepsilon
r_{1}}{2}}\right)^{5}\frac{1}{4}\left(\frac{r_{1}-17r_{1}\varepsilon}{2}\right)\mathrm{Opt}(\widetilde{I})-o(\mathrm{Opt}(\widetilde{I}))$
$\displaystyle=$ $\displaystyle\>\>\frac{(r_{1}-17\varepsilon
r_{1})^{6}}{384(6-r_{1}+17r_{1}\varepsilon)^{5}}\mathrm{Opt}(\widetilde{I})-o(\mathrm{Opt}(\widetilde{I}))$
$\displaystyle\geq$
$\displaystyle\>\>(1-16\varepsilon)\frac{(r_{1}-17\varepsilon
r_{1})^{6}}{384(6-r_{1}+17r_{1}\varepsilon)^{5}}\mathrm{Opt}(I)-o(\mathrm{Opt}(I))$
(16)

where the last inequality is due to 3.3.

Since $r_{1}\geq 0.91$, we obtain that the number of disjoint fitting $ML/SL$
triplets in the input sequence $I_{\sigma}$ is at least a constant fraction of
$\mathrm{Opt}(I)$. Next we will show that, in the packing of Best-Fit, each
fitting $ML/SL$ triplet in $I_{\sigma}(t^{\prime}_{\sigma}+1,t_{\sigma})$
corresponds to a unique bin of weight at least $3/2$.

######  Claim A.7.

Suppose there are $\tau$ number of disjoint fitting $ML/SL$ triplets in
$I_{\sigma}(t^{\prime}_{\sigma}+1,t_{\sigma})$. Then there will be at least
$\tau$ number of bins of weight at least $3/2$ in the packing
$\mathrm{BF}(I_{\sigma}(1,t_{\sigma}))$.

###### Proof.

Consider any $ML/SL$ triplet $q_{1},\ell_{1},q_{2},\ell_{2},q_{3},\ell_{3}$ in
the time segment $(t^{\prime}_{\sigma}+1,t_{\sigma})$. By the definition of an
$ML/SL$ triplet, it must be the case that in
$I_{\sigma}(t^{\prime}_{\sigma}+1,t_{\sigma})$, there can only be tiny items
in between $q_{1},\ell_{1},q_{2},\ell_{2},q_{3},\ell_{3}$. Now if $q_{1}$
opens a new bin, then $\ell_{1}$ must be packed along with $q_{1}$ as no tiny
item in between $q_{1}$ and $\ell_{1}$ can be packed with $q_{1}$ or can open
a new bin, by definition of $t^{\prime}_{\sigma}$. This leads to the creation
of an $ML/SL$ bin which has a weight $3/2$, as desired, and none of the items
from the future $ML/SL$ triplets can be packed in this bin.

On the other hand, suppose $q_{1}$ is placed in an already existing bin $B$.
If $B$ contained a large item before packing $q_{1}$, then we are done since
this will result in the formation of a bin of weight at least $3/2$ and no
item from a future $ML/SL$ triplet can be packed in this bin.

Hence, assume that $B$ did not contain any large items before packing $q_{1}$.
We consider two sub-cases depending on the volume of $B$ before $q_{1}$ is
packed in it. As the first sub-case, suppose $\mathrm{vol}(B)\geq 2/3$ before
packing $q_{1}$. By A.4, it must be the case that $W(B)\geq 1$ before packing
$q_{1}$. Hence, after packing $q_{1}$, the bin $B$ has a weight of at least
$3/2$. Moreover, since $\mathrm{vol}(B)\geq 2/3$ before packing $q_{1}$, we
have that $\mathrm{vol}(B)\geq 11/12$ after packing $q_{1}$, implying that no
item from a future $ML/SL$ triplet can be packed in $B$. Finally, we look at
the sub-case when $\mathrm{vol}(B)\leq 2/3$ before packing $q_{1}$. We can no
longer claim that packing $q_{1}$ makes the bin $B$ to have a weight of at
least $3/2$. However, A.3 guarantees that at any point, and before the arrival
of $q_{1}$ in particular, there can be at most two bins of load at most $2/3$.
Thus, if all of $q_{1},q_{2},q_{3}$ are packed in existing bins, this would
mean that one of them is packed in a bin of load at least $2/3$, thereby
resulting in the formation of bin of weight $3/2$. ∎

We can now complete the proof of Lemma 3.7. Inequality 16 gives us a lower
bound on the number of disjoint fitting $ML/SL$ triplets in the sequence
$I_{\sigma}(t^{\prime}_{\sigma}+1,t_{\sigma})$. A.7 tells us that, the number
of bins of weight $\geq 3/2$ in the packing
$\mathrm{BF}(I_{\sigma}(1,t_{\sigma}))$ is at least the number of disjoint
fitting $ML/SL$ triplets in the sequence
$I_{\sigma}(t^{\prime}_{\sigma}+1,t_{\sigma})$. Hence, w.h.p., the number of
bins of weight $\geq 3/2$ in $\mathrm{BF}(I_{\sigma}(1,t_{\sigma}))$ is at
least

$\displaystyle(1-16\varepsilon)\frac{(r_{1}-17\varepsilon
r_{1})^{6}}{384(6-r_{1}+17r_{1}\varepsilon)^{5}}\mathrm{Opt}(I)-o(\mathrm{Opt}(I))$

###  A.5 Proof of Lemma 3.8

Since $r_{2}=r_{2}(\sigma^{*})\geq 0.089$, which is a constant, we obtain that
the fraction of $SSS/MSS/MMS$ bins in
$\mathrm{Opt}(\widetilde{I}_{\sigma^{*}}(1,t_{\sigma^{*}}))$ is at least a
constant. This, in turn, means that there are a significant number of small
items. The rest of the analysis is as follows. First, we will show that in
$\widetilde{I}_{\sigma}(t^{\prime}_{\sigma}+1,t_{\sigma})$, there exist a good
number of consecutive $S$-triplets. Then, we will show that in the packing
$\mathrm{BF}(I_{\sigma}(1,t_{\sigma}))$, on an average, for two $S$-triplets,
there exists at least one bin of weight at least $3/2$. We thus obtain the
lemma. We will delve into the formal details now.

Since $r_{2}$ denotes the fraction of bins of type $SSS/MSS/MMS$ in
$\mathrm{Opt}(\widetilde{I}_{\sigma^{*}}(1,t_{\sigma^{*}}))$ and each of these
bins contains at least one small item, we have that the number of small items
in the instance $I$ is at least
$r_{2}\mathrm{Opt}(\widetilde{I}_{\sigma^{*}}(1,t_{\sigma^{*}}))$. By Eq. 3,
we know that

$\displaystyle\mathrm{Opt}(\widetilde{I}_{\sigma^{*}}(1,t_{\sigma^{*}}))$
$\displaystyle\geq\frac{1-17\varepsilon}{2}\mathrm{Opt}(\widetilde{I})$

Hence, we have that, in $\widetilde{I}$, there are at least

$\displaystyle\frac{r_{2}-17r_{2}\varepsilon}{2}\mathrm{Opt}(\widetilde{I})$

number of small items. On the other hand, there can be at most
$2\mathrm{Opt}(\widetilde{I})$ many large or medium items in $\widetilde{I}$
as at most $2$ such items fit into a bin. Thus, if $f_{S}$ denotes the
fraction of small items in the instance $\widetilde{I}$, we have

$\displaystyle
f_{S}\geq\frac{r_{2}-17r_{2}\varepsilon}{4+r_{2}-17r_{2}\varepsilon}$ (17)

We call a tuple of items $(S_{1},S_{2},S_{3})$ in the input sequence
$I_{\sigma}$ an $S$-triplet if the following conditions hold.

  * •

$S_{1}$ arrives before $S_{2}$ and $S_{2}$ arrives before $S_{3}$.

  * •

If we consider the sequence $\widetilde{I}_{\sigma}$, then $S_{1},S_{2},S_{3}$
form a substring in $\widetilde{I}$, i.e., in the original input sequence
$I_{\sigma}$, in between $S_{1},S_{2},S_{3}$, there can only be tiny items.

The next claim shows that in a randomly permuted input sequence, the number of
$S$-triplets in a time segment is proportional to the length of the segment.

######  Claim A.8.

Suppose $f_{S}$, the fraction of small items in $\widetilde{I}$, is at least
some positive constant. Let $n_{1},n_{2}$ be integers such that $1\leq
n_{1}\leq n_{2}\leq n$ and $n_{2}-n_{1}=\Theta(n)$. Then the maximum number of
mutually disjoint $S$-triplets in $I(n_{1}+1,n_{2})$ is at least

$\displaystyle\left(\frac{n_{2}-n_{1}}{3n}\right)f_{S}^{3}\left|\widetilde{I}\right|-o\left(\left|\widetilde{I}\right|\right)$

with high probability.

The proof of above claim mainly relies on concentration inequalities. However,
the proof is quite long, and hence, to maintain the flow of the section, we
defer the proof to Section A.10. We apply the above claim to our case by
choosing $n_{1}=n/4$, $n_{2}=n/2$, and we get that, with high probability, the
maximum number of mutually disjoint $S$-triplets in $I_{\sigma}(n/4,n/2)$ is
at least

$\displaystyle\frac{1}{4}\frac{f_{S}^{3}}{3}\left|\widetilde{I}\right|-o\left(\left|\widetilde{I}\right|\right)$
$\displaystyle\geq\frac{f_{S}^{3}}{12}\mathrm{Opt}(\widetilde{I})-o(\mathrm{Opt}(\widetilde{I}))$
$\displaystyle\geq\left(1-16\varepsilon\right)\frac{f_{S}^{3}}{12}\mathrm{Opt}(I)-o(\mathrm{Opt}(I))$

where the last inequality follows from 3.3. Recall that we are conditioning on
$E_{111}$ which implies that $t^{\prime}_{\sigma}\leq n/4$ and
$t_{\sigma}>n/2$. Thus, we get that, with high probability, in the random
sequence $I_{\sigma}(t^{\prime}_{\sigma}+1,t_{\sigma})$, the number of
mutually disjoint $S$-triplets is at least

$\displaystyle\left(1-16\varepsilon\right)\frac{f_{S}^{3}}{12}\mathrm{Opt}(I)-o(\mathrm{Opt}(I))$
(18)

Substituting Eq. 17 in Eq. 18, we obtain that, with high probability, the
number of mutually disjoint $S$-triplets in
$I_{\sigma}(t^{\prime}_{\sigma}+1,t_{\sigma})$ is at least

$\displaystyle\frac{1-16\varepsilon}{12}\left(\frac{r_{2}-17r_{2}\varepsilon}{4+r_{2}-17r_{2}\varepsilon}\right)^{3}{}\mathrm{Opt}(I)-o(\mathrm{Opt}(I))$
(19)

The next claim shows that the presence of $S$-triplets after
$t^{\prime}_{\sigma}$ is good for the performance of Best-Fit as a good number
of bins of weight $3/2$ will be created.

######  Claim A.9.

If there are $\varkappa$ many mutually disjoint $S$-triplets in
$I_{\sigma}(t^{\prime}_{\sigma}+1,t_{\sigma})$, then at least
$\varkappa/2-O(1)$ number of bins will be formed in
$\mathrm{BF}(I_{\sigma}(1,t_{\sigma}))$ that have a weight at least $3/2$.

The proof of the above claim is by case analysis and is deferred to Section
A.11.

Combining Eqs. 19 and A.9, we obtain that, with high probability, the number
of bins of weight $3/2$ in $\mathrm{BF}(I_{\sigma}(1,t_{\sigma}))$ is at least

$\displaystyle\frac{1-16\varepsilon}{24}\left(\frac{r_{2}-17r_{2}\varepsilon}{4+r_{2}-17r_{2}\varepsilon}\right)^{3}{}\mathrm{Opt}(I)-o(\mathrm{Opt}(I))$

###  A.6 Proof of Lemma 3.9

We will make use of Lemmas 3.7 and 3.8 and 3.5 to show the desired result,
conditioned on the event

$\displaystyle
E_{111}\coloneqq\left(t_{\sigma}^{\prime}\leq\frac{n}{4}\bigwedge\mathrm{vol}(T(1,t_{\sigma}))<12\varepsilon\mathrm{vol}(I_{\sigma}(1,t_{\sigma}))\bigwedge
t_{\sigma}>n/2\right)$

For simplicity, define the quantities

$\displaystyle\alpha_{1}=\frac{1-16\varepsilon}{384}\frac{(r_{1}-17r_{1}\varepsilon)^{6}}{(6-r_{1}+17r_{1}\varepsilon)^{5}}\qquad\qquad\alpha_{2}=\frac{1-16\varepsilon}{24}\left(\frac{r_{2}-17r_{2}\varepsilon}{4+r_{2}-17r_{2}\varepsilon}\right)^{3}$
(20)

For any permutation $\sigma$, we know that
$\beta(\sigma)+r_{1}(\sigma)+r_{2}(\sigma)=1-o(1)$.

  * •

Suppose there exists a permutation $\sigma^{*}$ for which $r_{1}\coloneqq
r_{1}(\sigma^{*})\geq 0.91$. 555such that $\sigma^{*}$ satisfies the high
probability event given by Eq.
3—$\mathrm{Opt}(\widetilde{I}_{\sigma^{*}}(1,t_{\sigma^{*}}))>\frac{1-17\varepsilon}{2}\mathrm{Opt}(\widetilde{I}_{\sigma^{*}})$
Then, from Lemma 3.7, we get that with high probability (conditioned on
$E_{111}$) Best-Fit creates at least

$\displaystyle a_{1}\geq\alpha_{1}\mathrm{Opt}(I)-o(\mathrm{Opt}(I))$

many bins of weight at least $3/2$, where $\alpha_{1}$ is given by Eq. 20. 3.1
guarantees that every bin (except possibly one) in the packing of Best-Fit has
a weight at least $1$. Consequently, we have

$\displaystyle
W(I_{\sigma}(1,t_{\sigma}))=\sum_{B\in\mathrm{BF}(I_{\sigma}(1,t_{\sigma}))}W(B)$
$\displaystyle\geq\frac{3}{2}\cdot
a_{1}+\mathrm{BF}(I_{\sigma}(1,t_{\sigma}))-a_{1}-1$
$\displaystyle\geq\mathrm{BF}(I_{\sigma}(1,t_{\sigma}))+\frac{a_{1}}{2}-1$
$\displaystyle\geq\mathrm{BF}(I_{\sigma}(1,t_{\sigma}))+\frac{\alpha_{1}}{2}\cdot\mathrm{Opt}(I)-o(\mathrm{Opt}(I))$
$\displaystyle\geq\mathrm{BF}(I_{\sigma}(1,t_{\sigma}))\left(1+\frac{\alpha_{1}}{3}\right)-o(\mathrm{Opt}(I))$

Combining this with 3.2 and using 3.5, we get that with high probability.

$\displaystyle\mathrm{BF}(I_{\sigma}(1,t_{\sigma}))$
$\displaystyle\leq\frac{\left(\frac{3}{2}-\frac{\beta(\sigma)}{2}\right)\left(\frac{1+24\varepsilon}{1-12\varepsilon}\right)}{1+\frac{\alpha_{1}}{3}}\cdot\mathrm{Opt}(I_{\sigma}(1,t_{\sigma}))+o(\mathrm{Opt}(I))$
$\displaystyle\leq\frac{\frac{3}{2}\left(\frac{1+24\varepsilon}{1-12\varepsilon}\right)}{1+\frac{\alpha_{1}}{3}}\cdot\mathrm{Opt}(I_{\sigma}(1,t_{\sigma}))+o(\mathrm{Opt}(I))$
$\displaystyle\leq\left(\frac{3}{2}-10^{-7}\right)\mathrm{Opt}(I_{\sigma}(1,t_{\sigma}))+o(\mathrm{Opt}(I))$
(substituting $r_{1}=0.91$ in Eq. 20 as $\alpha_{1}$ is increasing in $r_{1}$)
$\displaystyle\leq\left(\frac{3}{2}-2\varepsilon\right)\mathrm{Opt}(I_{\sigma}(1,t_{\sigma}))+o(\mathrm{Opt}(I))$

  * •

Suppose there exists a permutation $\sigma^{*}$ for which $r_{2}\coloneqq
r_{2}(\sigma^{*})\geq 0.089$. 666See Footnote 5 Then, from Lemma 3.8, we get
that with high probability (conditioned on $E_{111}$) Best-Fit creates at
least

$\displaystyle a_{2}\geq\alpha_{2}\mathrm{Opt}(I)-o(\mathrm{Opt}(I))$

many bins of weight at least $3/2$, where $\alpha_{2}$ is given by Eq. 20. 3.1
guarantees that every bin (except possibly one) in the packing of Best-Fit has
a weight at least $1$. Consequently, we have

$\displaystyle\sum_{B\in\mathrm{BF}(I_{\sigma}(1,t_{\sigma}))}W(B)$
$\displaystyle\geq\frac{3}{2}\cdot
a_{2}+\mathrm{BF}(I_{\sigma}(1,t_{\sigma}))-a_{2}-1$
$\displaystyle\geq\mathrm{BF}(I_{\sigma}(1,t_{\sigma}))+\frac{a_{2}}{2}-1$
$\displaystyle\geq\mathrm{BF}(I_{\sigma}(1,t_{\sigma}))+\frac{\alpha_{2}}{2}\cdot\mathrm{Opt}(I)-o(\mathrm{Opt}(I))$
$\displaystyle\geq\mathrm{BF}(I_{\sigma}(1,t_{\sigma}))\left(1+\frac{\alpha_{2}}{3}\right)-o(\mathrm{Opt}(I))$

Combining this with 3.2 and using 3.5, we get that with high probability.

$\displaystyle\mathrm{BF}(I_{\sigma}(1,t_{\sigma}))$
$\displaystyle\leq\frac{\left(\frac{3}{2}-\frac{\beta(\sigma)}{2}\right)\left(\frac{1+24\varepsilon}{1-12\varepsilon}\right)}{1+\frac{\alpha_{2}}{3}}\cdot\mathrm{Opt}(I_{\sigma}(1,t_{\sigma}))+o(\mathrm{Opt}(I))$
$\displaystyle\leq\frac{\frac{3}{2}\left(\frac{1+24\varepsilon}{1-12\varepsilon}\right)}{1+\frac{\alpha_{2}}{3}}\cdot\mathrm{Opt}(I_{\sigma}(1,t_{\sigma}))+o(\mathrm{Opt}(I))$
$\displaystyle\leq\left(\frac{3}{2}-10^{-7}\right)\mathrm{Opt}(I_{\sigma}(1,t_{\sigma}))+o(\mathrm{Opt}(I))$
(substituting $r_{2}=0.089$ in Eq. 20 as $\alpha_{2}$ is increasing in
$r_{2}$)
$\displaystyle\leq\left(\frac{3}{2}-2\varepsilon\right)\mathrm{Opt}(I_{\sigma}(1,t_{\sigma}))+o(\mathrm{Opt}(I))$

  * •

Suppose for all the permutations $\sigma$ satisfying the high probability
event given by Eq. 3, we have $r_{1}(\sigma)<0.91$ and $r_{2}(\sigma)<0.089$.
Then $\beta(\sigma)\geq 0.0001$ for each such permutation. Hence, by 3.5, we
have that for all permutations $\sigma$,

$\displaystyle\mathrm{BF}(I_{\sigma}(1,t_{\sigma}))$
$\displaystyle\leq\left(\frac{3}{2}-\frac{\beta(\sigma)}{2}\right)\left(\frac{1+24\varepsilon}{1-12\varepsilon}\right)\mathrm{Opt}(I_{\sigma}(1,t_{\sigma})+O(1)$
$\displaystyle\leq\left(\frac{3}{2}-10^{-6}\right)\mathrm{Opt}(I_{\sigma}(1,t_{\sigma})+O(1)$
$\displaystyle\leq\left(\frac{3}{2}-2\varepsilon\right)\mathrm{Opt}(I_{\sigma}(1,t_{\sigma})+O(1)$

Thus, we have shown that, the desired bound on
$\mathrm{BF}(I_{\sigma}(1,t_{\sigma}))$ holds for all but a negligible
fraction of permutations $\sigma$, i.e.,

$\displaystyle\mathbb{P}\left[\mathrm{BF}(I_{\sigma}(1,t_{\sigma}))\leq\left(\frac{3}{2}-2\varepsilon\right)\mathrm{Opt}(I_{\sigma}(1,t_{\sigma}))+o(\mathrm{Opt}(I))\bigg{|}E_{111}\right]\geq
1-o(1)$

as desired.

###  A.7 Proof of Lemma 3.10

Using Lemma 3.1, we have that the following is true with high probability
since $t^{\prime}_{\sigma}>n/4$.

$\displaystyle\mathrm{Opt}(I_{\sigma}(1,t^{\prime}_{\sigma}))\geq\mathrm{Opt}(I_{\sigma}(1,n/4))\geq\frac{1-\delta}{4}\mathrm{Opt}(I)$
$\displaystyle\geq\frac{1-\delta}{4}\mathrm{Opt}(I_{\sigma}(1,t_{\sigma}))$
(21)

Now, by definition of $t_{\sigma}^{\prime}$, all the bins (except possibly
one) in $\mathrm{BF}(I_{\sigma}(1,t_{\sigma}^{\prime}))$ must have load
greater than $3/4$. Hence, let $\mathcal{B}_{1}$ be the set of bins in
$\mathrm{BF}(I_{\sigma}(1,t_{\sigma}))$ that have a load greater than $3/4$.
We have
$\left|\mathcal{B}_{1}\right|\geq\mathrm{BF}(I_{\sigma}(1,t^{\prime}_{\sigma}))-1\geq\mathrm{Opt}(I_{\sigma}(1,t^{\prime}_{\sigma}))-1$.
Then, using Eq. 21, we obtain that

$\displaystyle\mathrm{vol}(\mathcal{B}_{1})$
$\displaystyle\geq\frac{3}{4}(\mathrm{Opt}(I_{\sigma}(1,t_{\sigma}^{\prime}))-1)$
$\displaystyle\geq\frac{3}{4}\frac{1-\delta}{4}\mathrm{Opt}(I_{\sigma}(1,t_{\sigma}))-\frac{3}{4}$
$\displaystyle\geq\frac{1}{6}\mathrm{Opt}(I_{\sigma}(1,t_{\sigma}))-\frac{3}{4}$
(22)

with high probability, for small enough $\delta$.

By definition of $t_{\sigma}$, all the bins (except possibly one) in
$\mathrm{BF}(I_{\sigma}(1,t_{\sigma}))$ have a load at least $2/3$. Let the
set of bins in $\mathrm{BF}(I_{\sigma}(1,t_{\sigma}))$ with load $\geq 2/3$
but $\leq 3/4$ at time $t_{\sigma}$ be $\mathcal{B}_{2}$.

$\displaystyle\mathrm{BF}(I_{\sigma}(1,t_{\sigma}))$
$\displaystyle\leq|\mathcal{B}_{1}|+|\mathcal{B}_{2}|+2$
$\displaystyle\leq\frac{4}{3}\mathrm{vol}(\mathcal{B}_{1})+\frac{3}{2}\Big{(}(\mathrm{vol}(I_{\sigma}(1,t_{\sigma}))-\mathrm{vol}(\mathcal{B}_{1})\Big{)}+2$
$\displaystyle\leq\frac{3}{2}\mathrm{vol}(I_{\sigma}(1,t_{\sigma}))-\frac{\mathrm{vol}(\mathcal{B}_{1})}{6}+2$
$\displaystyle\leq\frac{3}{2}\mathrm{Opt}(I_{\sigma}(1,t_{\sigma}))-\frac{1}{6\cdot
6}\mathrm{Opt}(I_{\sigma}(1,t_{\sigma}))+\frac{1}{8}+2\quad\text{(using
\lx@cref{creftype~refnum}{eq:vol-b1})}$
$\displaystyle\leq\left(\frac{3}{2}-\frac{1}{36}\right)\mathrm{Opt}(I_{\sigma}(1,t_{\sigma}))+\frac{17}{8}$

###  A.8 Proof of 3.6

Let $\mathcal{B}_{\leq 3/4}$ denote the set of bins in the packing
$\mathrm{BF}(I_{\sigma}(1,t_{\sigma}))$ that have a load of at most $3/4$. Let
$t_{1},t_{2},\dots,t_{r}$ denote the tiny items in the set of bins
$\mathcal{B}_{\leq 3/4}$, indexed in the order of their arrival, and let
$\tau(1),\tau(2),\dots,\tau(r)$ denote their respective arrival times, i.e.,
their indices in the input sequence $I_{\sigma}$. Also, for $i\in[r]$, denote
the bin into which $t_{i}$ was packed by $B_{i}$, and let
$\mathrm{vol}\left(B^{(t)}\right)$ denote the volume of bin $B$ after the
$t^{\mathrm{th}}$ item in the input sequence $I_{\sigma}$ is packed. Note that
the $B_{i}$-s may not necessarily be different since two tiny items can be
packed into the same bin.

We claim that for all $i\in[r-1]$,

$\displaystyle\mathrm{vol}\left(B_{i+1}^{\tau(i+1)}\right)\geq\mathrm{vol}\left(B_{i}^{\tau(i)}\right)+s(t_{i+1})$
(23)

holds. To see why this is true, first consider the case when $B_{i}=B_{i+1}$.
Then, the above condition holds since the volume of bin $B_{i}$ would have
increased by at least $s(t_{i+1})$ after packing $t_{i+1}$ (possibly besides
some items between $t_{i},t_{i+1}$). So, suppose $B_{i}\neq B_{i+1}$. Since
$B_{i}\in\mathcal{B}_{\leq 3/4}$ and $s\left(t_{i+1}\right)\leq 1/4$, Best-Fit
must have chosen $B_{i+1}$ to pack $t_{i+1}$ because
$\mathrm{vol}\left(B_{i}^{(\tau(i))}\right)\leq\mathrm{vol}\left(B_{i+1}^{(\tau(i))}\right)$.
Since
$\mathrm{vol}\left(B_{i+1}^{(\tau(i+1))}\right)\geq\mathrm{vol}\left(B_{i+1}^{(\tau(i))}\right)+s(t_{i+1})$,
Eq. 23 holds. As a consequence, combining Eq. 23 for all $i\in[r-1]$, we
obtain that

$\displaystyle\frac{3}{4}\geq\mathrm{vol}\left(B_{r}^{(\tau(r))}\right)\geq\mathrm{vol}\left(B_{1}^{(\tau(1))}\right)+\sum_{i=2}^{r}s(t(i))\geq\sum_{i=1}^{r}s(t(i))$

Hence, we obtain that the volume of tiny items in the set of bins
$\mathcal{B}_{\leq 3/4}$ is at most $3/4$. However, recall from the lemma
statement that the total volume of tiny items in the sequence
$I_{\sigma}(1,t_{\sigma})$ is at least
$12\varepsilon\mathrm{vol}(I_{\sigma}(1,t_{\sigma}))$. Hence, at least
$12\varepsilon\mathrm{vol}(I_{\sigma}(1,t_{\sigma}))-3/4$ volume of tiny items
must be present in bins of load greater than $3/4$ in the packing
$\mathrm{BF}(I_{\sigma}(1,t_{\sigma}))$. This implies that there are at least
$\left\lfloor
12\varepsilon\mathrm{vol}(I_{\sigma}(1,t_{\sigma}))\right\rfloor$ many bins of
load greater than $3/4$ in the packing
$\mathrm{BF}(I_{\sigma}(1,t_{\sigma}))$.

###  A.9 Proofs of 3.8 and A.6

In this section, we will prove a lemma generalizing both 3.8 and A.6.

First, we define some notation. Let $P\subseteq[0,1]$ be a range of sizes and
let $Q\subseteq[0,1]$ be another range of sizes such that $Q\cap P=\emptyset$,
i.e., they are disjoint. Further, we say an item is of type $P$ (respectively,
type $Q$) if its size lies in the range $P$ (respectively, $Q$). Now, consider
an input sequence $I_{\sigma}$. Let $\widehat{I}$ denote the list $I$ obtained
after removing all the items not of type $P/Q$. Similarly,
$\widehat{I}_{\sigma}$ denotes the sequence $I_{\sigma}$ obtained after
deleting the items not of type $P/Q$. A pair of items $(p,q)$ in $I_{\sigma}$
is said to be a _fitting $PQ$ pair_ if the item $p$ is of type $P$ and item
$q$ is of type $Q$ and $p+q\leq 1$. Further, a sextuplet of items
$(p_{1},q_{1},p_{2},q_{2},p_{3},q_{3})$ in $I_{\sigma}$ is said to be a
_fitting $PQ$ triplet_ if

  * •

every pair $(p_{i},q_{i})$ is a fitting $PQ$ pair.

  * •

the items $p_{1},q_{1},p_{2},q_{2},p_{3},q_{3}$ arrive in that order.

  * •

there are no items of type $P/Q$ in between them, i.e., in the sequence
$\widehat{I}_{\sigma}$, the items $p_{1},q_{1},p_{2},q_{2},p_{3},q_{3}$ appear
consecutively.

We will now state the general lemma and see how 3.8 and A.6 reduce to it.

######  Lemma A.4.

Suppose $\mathrm{Opt}(\widehat{I})\to\infty$. Let $\Gamma$ denote a maximum
cardinality set of disjoint fitting $PQ$ pairs in $I$. Define
$x\coloneqq\left|\Gamma\right|$ and $y$ to be the number of items in
$\widehat{I}$ that are not part of any pair in $\Gamma$. Suppose there exist
positive constants $u,v$ such that $x\geq u\mathrm{Opt}(\widehat{I})$ and
$y\leq v\mathrm{Opt}(\widehat{I})$. Then, for any two arbitrary $a,b$ such
that $1\leq a\leq b\leq n$ and $b-a=\Theta(n)$, we have that the number of
disjoint fitting $PQ$ triplets in the sequence $I_{\sigma}(a+1,b)$ is at least

$\displaystyle\frac{1}{48}\left(\frac{b-a}{n}\right)\left(\frac{1}{2+\frac{y}{x}}\right)^{5}x-o(x)$

with high probability, where $\sigma$ is a uniformly randomly chosen
permutation.

###### Proof of 3.8.

In Lemma A.4, substitute type $P$ with type $M$ and type $Q$ with type $L$.
Then $\widehat{I}$ will just be $I^{\prime}$, and $x$ will just be
$d^{\prime}\geq u\mathrm{Opt}(I^{\prime})$. We need to calculate what the
value of $v$ will be. Since, in $\mathrm{Opt}(I^{\prime})$, at least $u$
fraction of bins are of type $LM$, there can be at most $(1-u)$ fraction of
bins of type $L/MM$, which in turn, implies that there can be at most
$2(1-u)\mathrm{Opt}(I^{\prime})$ number of items in $I^{\prime}$ that are not
part of any fitting $ML$ pair. Hence $y\leq 2(1-u)\mathrm{Opt}(I^{\prime})$.
Finally, we substitute $b=n_{2},a=n_{1}$ to obtain that the number of disjoint
fitting $ML$ triplets in $I_{\sigma}(n_{1}+1,n_{2})$ is at least

$\displaystyle\frac{1}{48}\left(\frac{n_{2}-n_{1}}{n}\right)\left(\frac{1}{2+\frac{y}{x}}\right)^{5}x-o(x)\geq\>\>$
$\displaystyle\frac{1}{48}\left(\frac{n_{2}-n_{1}}{n}\right)\left(\frac{1}{2+\frac{2-2u}{u}}\right)^{5}d^{\prime}-o(d^{\prime})$
$\displaystyle\geq\>\>$
$\displaystyle\frac{u^{5}}{1536}\left(\frac{n_{2}-n_{1}}{n}\right)d^{\prime}-o(d^{\prime})$

with high probability. ∎

###### Proof of A.6.

In Lemma A.4, substitute type $P$ with type $M/S$ and type $Q$ with type $L$.
Then $\widehat{I}$ will just be $\widetilde{I}$, and $x$ will just be
$\kappa\geq u\mathrm{Opt}(\widetilde{I})$. Since, in
$\mathrm{Opt}(\widetilde{I})$, at least $u$ fraction of bins are of type
$ML/SL$, there can be at most $(1-u)$ fraction of bins of type
$L/MM/MSS/MMS/SSS$, which in turn, implies that there can at most
$3(1-u)\mathrm{Opt}(\widetilde{I})$ number of items in $\widetilde{I}$ that
are not part of any fitting $ML/SL$ pair. Hence $y\leq
3(1-u)\mathrm{Opt}(\widetilde{I})$. Finally, we substitute $b=n_{2},a=n_{1}$
to obtain that the number of disjoint fitting $ML/SL$ triplets in
$I_{\sigma}(n_{1}+1,n_{2})$ is at least

$\displaystyle\frac{1}{48}\left(\frac{n_{2}-n_{1}}{n}\right)\left(\frac{1}{2+\frac{y}{x}}\right)^{5}x-o(x)\geq\>\>$
$\displaystyle\frac{1}{48}\left(\frac{n_{2}-n_{1}}{n}\right)\left(\frac{1}{2+\frac{3-3u}{u}}\right)^{5}\kappa-o(\kappa)$
$\displaystyle\geq\>\>$
$\displaystyle\frac{u^{5}}{48(3-u)^{5}}\left(\frac{n_{2}-n_{1}}{n}\right)\kappa-o(\kappa)$

with high probability. ∎

We will now prove the general claim.

###### Proof of Lemma A.4.

Let the pairs in $\Gamma$ be ordered as
$(p_{1},q_{1}),(p_{2},q_{2}),\cdots,(p_{x},q_{x})$ where
$p_{1},p_{2},\dots,p_{x}$ are in non-decreasing order. At times, we will use
$\Gamma$ to denote the set
$\\{p_{1},p_{2},\dots,p_{x},q_{1},q_{2},\dots,q_{x}\\}$. What usage we are
referring to will be clear from the context. All the expectation, variance,
and covariance calculations will be computed over the randomness of $\sigma$.
Define $z\coloneqq\left|\widehat{I}\right|$. Observe that, by definitions of
$x,y$, it follows that $z=2x+y$.

For a given index $i$, let $X_{i}$ be the random variable that denotes the
number of items of type $P/Q$ in $I_{\sigma}(1,i)$. We first estimate $X_{a}$
and $X_{b}$. Let $Y_{j}$ be the indicator random variable that denotes if the
$j^{\mathrm{th}}$ item in $I_{\sigma}$ is of type $P/Q$. Then,
$X_{i}=\sum_{j=1}^{i}Y_{j}$, and since there are $z$ $P/Q$ items in total, we
get

$\displaystyle\mathbb{P}\left[Y_{j}=1\right]=\frac{z}{n}\quad\text{and}\quad\mathrm{Var}\left[Y_{j}\right]=\mathbb{E}\left[Y_{j}^{2}\right]-\mathbb{E}\left[Y_{j}\right]^{2}\leq\frac{z}{n}$

Using linearity of expectations, we obtain

$\displaystyle\mathbb{E}\left[X_{i}\right]=i\frac{z}{n}$ (24)

Next, we show that $Y_{j},Y_{k}$ are negatively correlated for $j\neq k$. Note
that $\mathbb{P}\left[Y_{j}=1|Y_{k}=1\right]=\frac{z-1}{n-1}$. This is because
once the $k^{\mathrm{th}}$ position is occupied by a $P/Q$ item, there are
$z-1$ number of $P/Q$ items left to occupy the $j^{\mathrm{th}}$ position
among the remaining $n-1$ items. Since $\frac{z-1}{n-1}<\frac{z}{n}$, we have
that $\mathbb{P}\left[Y_{j}=1|Y_{k}=1\right]<\mathbb{P}\left[Y_{j}=1\right]$.
This implies that $\mathbb{P}\left[Y_{j}=1\land
Y_{k}=1\right]<\mathbb{P}\left[Y_{j}=1\right]\mathbb{P}\left[Y_{k}=1\right]$.
Hence,

$\displaystyle\mathrm{Cov}\left[Y_{j},Y_{k}\right]=\mathbb{E}\left[Y_{j}Y_{k}\right]-\mathbb{E}\left[Y_{j}\right]\mathbb{E}\left[Y_{k}\right]<0$

This gives us the variance bound

$\displaystyle\mathrm{Var}\left[X_{i}\right]=\sum_{j=1}^{i}\mathrm{Var}\left[Y_{j}\right]+2\sum_{1\leq
j<k\leq n}\mathrm{Cov}\left[Y_{j},Y_{k}\right]\leq i\frac{z}{n}$ (25)

Hence using Eq. 24, Eq. 25 and Chebyshev’s inequality, we obtain

$\displaystyle\mathbb{P}\left[\left|X_{a}-\frac{z}{n}a\right|\geq
z^{2/3}\right]\leq\frac{\mathrm{Var}\left[X_{a}\right]}{z^{4/3}}\leq\frac{a(z/n)}{z^{4/3}}=O\left(\frac{1}{z^{1/3}}\right)$
$\displaystyle\mathbb{P}\left[\left|X_{b}-\frac{z}{n}b\right|\geq
z^{2/3}\right]\leq\frac{\mathrm{Var}\left[X_{b}\right]}{z^{4/3}}\leq\frac{b(z/n)}{z^{4/3}}=O\left(\frac{1}{z^{1/3}}\right)$

Hence,

$\displaystyle X_{a}\leq a\frac{z}{n}+z^{2/3}\quad\text{and}\quad X_{b}\geq
b\frac{z}{n}-z^{2/3}$ (26)

occur simultaneously with probability at least $1-O(1/z^{1/3})$.

We now argue that we have a good number of fitting $PQ$ triplets in between
the above indices $a,b$ using a deletion argument. Observe that randomly
shuffling $I$ and then removing all the items not of type $P/Q$ gives us a
random permutation of $\widehat{I}$. We group the $z$ items in $\widehat{I}$
into $z/6$ number of sextuplets as shown below.

$\displaystyle\underbrace{*****\>*}_{\mathrm{Sextuplet}\>S_{1}}\underbrace{*****\>*}_{\mathrm{Sextuplet}\>S_{2}}\cdots\underbrace{*****\>*}_{\mathrm{Sextuplet}\>S_{z/6}}$

Let $F_{i}$ be the indicator random variable that takes value $1$ if the
sextuplet $S_{i}$ is a $PQ$ triplet, where all the $6$ items belong to
$\Gamma$, and $0$ otherwise. (It’s not imperative that the items must be from
$\Gamma$; they can be from $\widehat{I}\setminus\Gamma$ too. However, this
restriction that we impose will ease the calculations in the concentration
analysis that comes later.) We calculate the probability of $F_{i}=1$ as
follows. The first item needs to be of type $P$ and from $\Gamma$; there are
$x$ choices for this to happen among a total of $z$. Then, among the remaining
$z-1$ items, we need to select one of $x$ items of type $Y$ from $\Gamma$.
Then, for the third item, we have $x-1$ choices (as we already chose the first
item to be of type $P$) among $z-2$. We continue in this manner to obtain that

$\displaystyle\mathbb{P}\left[F_{i}=1\right]$
$\displaystyle=\frac{x}{z}\cdot\frac{x}{z-1}\cdot\frac{x-1}{z-2}\cdot\frac{x-1}{z-3}\cdot\frac{x-2}{z-4}\cdot\frac{x-2}{z-5}$
$\displaystyle=\frac{x}{2x+y}\cdot\frac{x}{2x+y-1}\cdot\frac{x-1}{2x+y-2}\cdot\frac{x-1}{2x+y-3}\cdot\frac{x-2}{2x+y-4}\cdot\frac{x-2}{2x+y-5}$
$\displaystyle=\frac{1}{(2+\frac{y}{x})^{6}}-o(1)$ (27)

Now, we proceed to calculate the probability that these $PQ$ triplets are
indeed fitting. Towards this, we construct a bipartite graph as follows. The
vertex set is given by $\Gamma_{P}\cup\Gamma_{Q}$ where

$\displaystyle\Gamma_{P}=\\{p_{1},p_{2},\dots,p_{x}\\}\quad\text{and}\quad\Gamma_{Q}=\\{q_{1},q_{2},\dots,q_{x}\\}.$

For every $i\in[x]$, we draw an edge between
$(p_{i},q_{i}),(p_{i},q_{i+1}),\dots,(p_{i},q_{x})$. Note that an edge between
$p_{i}$ and $q_{j}$ implies that the pair $(p_{i},q_{j})$ is fitting. This is
because $p_{i}+q_{j}\leq p_{j}+q_{j}\leq 1$ as $(p_{j},q_{j})$ is fitting. Let
us denote this graph by $G_{\Gamma}$. An example of $G_{\Gamma}$ when $x=4$
looks like Fig. 4.

Figure 4: The bipartite graph $G_{\Gamma}$ when $x=4$. Every edge corresponds
to a fitting $PQ$ pair. As a side note, the converse may not be true.

Using the graph $G_{\Gamma}$, we now proceed to compute the probability that a
$PQ$ triplet is indeed fitting. Define $H_{i}$ to be the indicator random
variable which takes value $1$ when the sextuplet $S_{i}$ is a fitting $PQ$
triplet _and_ each of the three consecutive $PQ$ pairs in $S_{i}$ corresponds
to an edge in $G_{\Gamma}$.

Conditioning on $F_{i}=1$ (i.e., $S_{i}$ is a $PQ$ triplet), the probability
that the first $PQ$ pair corresponds to an edge in $G_{\Gamma}$ is given by
$\frac{x(x+1)/2}{x^{2}}$ as there are $x(x+1)/2$ number of edges in
$G_{\Gamma}$ and $x^{2}$ number of $PQ$ pairs are possible in total. Once the
first $PQ$ pair is chosen such that it corresponds to an edge, all the edges
incident on both these vertices will be deleted, as none of these edges can be
the candidates for the $PQ$ pairs chosen next. The number of these deleted
edges will be at most $2x-1$. (This worst case happens when the $PQ$ pair
picked is $(p_{1},q_{x})$.) Therefore, the number of remaining edges will be
at least $x(x+1)/2-(2x-1)=(x-2)(x-1)/2$. Hence, the probability that the
second $PQ$ pair corresponds to an edge in $G_{\Gamma}$ obtained after
removing the edges incident on the vertices corresponding to the first $PQ$
pair is at least $\frac{(x-2)(x-1)/2}{(x-1)^{2}}$. Similarly, the probability
that the third $PQ$ pair corresponds to an edge in $G_{\Gamma}$ obtained after
removing the edges incident on the vertices corresponding to the first $PQ$
pairs is at least $\frac{(x-4)(x-3)/2}{(x-2)^{2}}$. Therefore,

$\displaystyle\mathbb{P}\left[H_{i}=1|F_{i}=1\right]$
$\displaystyle\geq\frac{x(x+1)/2}{x^{2}}\cdot\frac{(x-2)(x-1)/2}{(x-1)^{2}}\cdot\frac{(x-4)(x-3)/2}{(x-2)^{2}}$
$\displaystyle=\left(\frac{1}{2}+O(1/x)\right)\left(\frac{1}{2}-O(1/x)\right)\left(\frac{1}{2}-O(1/x)\right)=\frac{1}{8}-O(1/x)$
(28)

Now, we compute an upper bound on $\mathbb{P}\left[H_{i}=1|F_{i}=1\right]$ in
a way similar to how we computed the lower bound. Assuming $F_{i}=1$, the
probability that the first $PQ$ pair corresponds to an edge in $G_{\Gamma}$
remains $\frac{x(x+1)/2}{x^{2}}$ as before. The probability that the second
$PQ$ pair corresponds to an edge in $G_{\Gamma}$ obtained after removing the
edges incident on the vertices in the first $PQ$ pair is at most
$\frac{x(x+1)/2-x}{x^{2}}=\frac{x-1}{2x}$ because at least $x$ edges will be
lost due to the first $PQ$ pair. (This case happens when $(p_{1},q_{1})$ form
the first pair.) Similarly, at least $(x-1)$ edges will be lost due to the
second $PQ$ pair. Therefore, the probability that the third $PQ$ pair
corresponds to an edge in the remaining graph is
$\frac{x(x+1)/2-x-(x-1)}{(x-2)^{2}}=\frac{x-1}{2(x-2)}$. Therefore

$\displaystyle\mathbb{P}\left[H_{i}=1|F_{i}=1\right]$
$\displaystyle\leq\frac{x+1}{2x}\cdot\frac{x}{2(x-1)}\cdot\frac{x-1}{2(x-2)}$
$\displaystyle=\frac{1}{8}+O(1/x)$ (29)

Now, a lower bound on the number of fitting $PQ$ triplets in the sequence
$I_{\sigma}(a+1,b)$ is given by the random variable

$\displaystyle
S_{(a,b)}=H_{(\frac{a}{6}+1)\frac{z}{n}}+\dots+H_{\frac{b}{6}\frac{z}{n}}$

By linearity of expectations, Section A.9, and Section A.9 we obtain

$\displaystyle\mathbb{E}\left[S_{(a,b)}\right]\geq\frac{b-a}{6}\cdot\frac{z}{n}\cdot\frac{1}{8}\cdot\left(\frac{1}{2+\frac{y}{x}}\right)^{6}-o(z)$
(30)

Now, to prove concentration around the expectation, we compute
$\mathrm{Var}\left[S_{(a,b)}\right]$ and use Chebyshev’s inequality. For any
$i$, since $H_{i}$ takes values $0,1$,

$\displaystyle\mathrm{Var}\left[H_{i}\right]=\mathbb{E}\left[H_{i}^{2}\right]-\mathbb{E}\left[H_{i}\right]^{2}\leq
1$

Now, consider any two sextuplets $S_{j},S_{k}$. We claim that the events
$H_{j}=1$ and $H_{k}=1$ are weakly correlated.

$\displaystyle\mathbb{P}\left[H_{j}=1|H_{k}=1\right]$
$\displaystyle=\mathbb{P}\left[F_{j}=1|H_{k}=1\right]\mathbb{P}\left[H_{j}=1|F_{j}=1,H_{k}=1\right]$
$\displaystyle\>\>+\mathbb{P}\left[F_{j}=0|H_{k}=1\right]\mathbb{P}\left[H_{j}=1|F_{j}=0,H_{k}=1\right]$

However, for the event $H_{j}=1$ to occur in the first place, $F_{j}=1$ must
happen. Therefore,

$\displaystyle\mathbb{P}\left[H_{j}=1|H_{k}=1\right]$
$\displaystyle=\mathbb{P}\left[F_{j}=1|H_{k}=1\right]\cdot\mathbb{P}\left[H_{j}=1|F_{j}=1,H_{k}=1\right]$
(31)

The quantity $\mathbb{P}\left[F_{j}=1|H_{k}=1\right]$, and an upper bound on
$\mathbb{P}\left[H_{j}=1|F_{j}=1,H_{k}=1\right]$ can be calculated similar to
Section A.9 and Section A.9, respectively, except that, instead of $x,z$, we
substitute $x-3,z-3$, respectively. This is because we are conditioning on
$H_{k}=1$, which means that we are at a loss of three items of type $P$ and
three items of type $Q$ from $\Gamma$. Therefore, we obtain that

$\displaystyle\mathbb{P}\left[H_{j}=1|H_{k}=1\right]$
$\displaystyle\leq\left(\frac{x-3}{2x+y-6}\frac{x-3}{2x+y-7}\frac{x-4}{2x+y-8}\frac{x-4}{2x+y-9}\frac{x-5}{2x+y-10}\frac{x-5}{2x+y-11}\right)$
$\displaystyle\>\>\times\left(\frac{(x-3)+1}{2(x-3)}\cdot\frac{(x-3)}{2((x-3)-1)}\cdot\frac{(x-3)-1}{2((x-3)-2)}\right)$
$\displaystyle\leq\frac{x}{2x+y}\frac{x}{2x+y-1}\frac{x-1}{2x+y-2}\frac{x-1}{2x+y-3}\frac{x-2}{2x+y-4}\frac{x-2}{2x+y-5}$
$\displaystyle\>\>\times\left(\frac{1}{2}+O(1/x)\right)^{3}$
$\displaystyle\leq\mathbb{P}\left[F_{j}=1\right]\cdot\left(\frac{1}{8}+O(1/x)\right)$
(32)

Using Section A.9, Eq. 31,we get the covariance estimate

$\displaystyle\mathrm{Cov}\left[H_{j},H_{k}\right]$
$\displaystyle=\mathbb{P}\left[H_{j}=1\right]\cdot(\mathbb{P}\left[H_{j}=1|H_{k}=1\right]-\mathbb{P}\left[H_{k}=1\right])$
$\displaystyle=\mathbb{P}\left[H_{j}=1|F_{j}=1\right]\mathbb{P}\left[F_{j}=1\right]\cdot(\mathbb{P}\left[H_{j}=1|H_{k}=1\right]-\mathbb{P}\left[H_{k}=1|F_{k}=1\right]\mathbb{P}\left[F_{k}=1\right])$

An upper bound on $\mathbb{P}\left[H_{j}=1|F_{j}=1\right]$ is given by Section
A.9, an upper bound on $\mathbb{P}\left[H_{j}=1|H_{k}=1\right]$ is given by
Eq. 32, and a lower bound on $\mathbb{P}\left[H_{k}=1|F_{k}=1\right]$ is given
by Section A.9. Thus, we obtain

$\displaystyle\mathrm{Cov}\left[H_{j},H_{k}\right]$
$\displaystyle\leq\mathbb{P}\left[F_{j}=1\right]\left(\frac{1}{8}+O(1/x)\right)\cdot\left(\mathbb{P}\left[F_{j}=1\right]\left(\frac{1}{8}+O(1/x)\right)-\mathbb{P}\left[F_{k}=1\right]\left(\frac{1}{8}-O(1/x)\right)\right)$
$\displaystyle\leq(\mathbb{P}\left[F_{j}=1\right])^{2}\left(\frac{1}{8}+O(1/x)\right)\cdot
O(1/x)\leq O(1/x)$ (33)

where the penultimate inequality follows since
$\mathbb{P}\left[F_{j}=1\right]=\mathbb{P}\left[F_{k}=1\right]$. Now using
Section A.9, since $z=2x+y=(2+\frac{y}{x})x=O(x)$ as $y/x$ is upper bounded by
some constant as per the lemma statement, we get

$\displaystyle\mathrm{Var}\left[S_{(a,b)}\right]$
$\displaystyle=\sum_{i=(\frac{a}{6}+1)\frac{z}{n}}^{\frac{b}{6}\frac{z}{n}}\mathrm{Var}\left[H_{i}\right]+2\sum_{(\frac{a}{6}+1)\frac{z}{n}\leq
j<k\leq\frac{a}{6}\frac{z}{n}}\mathrm{Cov}\left[H_{j},H_{k}\right]$
$\displaystyle\leq\frac{z}{6}+O(z^{2}/x)=O(x)$ (34)

Thus using Chebyshev’s inequality and Eq. 30, Section A.9

$\displaystyle\mathbb{P}\left[S_{(a,b)}\leq\mathbb{E}\left[S_{(a,b)}\right]-\left(\mathbb{E}\left[S_{(a,b)}\right]\right)^{2/3}\right]$
$\displaystyle\leq\mathbb{P}\left[\left|S_{(a,b)}-\mathbb{E}\left[S_{(a,b)}\right]\right|\geq\left(\mathbb{E}\left[S_{(a,b)}\right]\right)^{2/3}\right]$
$\displaystyle\leq\frac{\mathrm{Var}\left[S_{(a,b)}\right]}{\left(\mathbb{E}\left[S_{(a,b)}\right]\right)^{4/3}}$
$\displaystyle\leq O\left(\frac{x}{x^{4/3}}\right)$
$\displaystyle=O\left(\frac{1}{x^{1/3}}\right)$

This thus gives us
$S_{(a,b)}\geq\frac{b-a}{n}\cdot\frac{1}{48}\left(\frac{1}{2+\frac{y}{x}}\right)^{5}x-o(x)$
with high probability.

Hence, the number of disjoint fitting $PQ$ triplets in $\widehat{I}_{\sigma}$
between the indices $((a/n)z,(b/n)z)$ is at least
$\frac{b-a}{n}\cdot\frac{1}{48}\left(\frac{1}{2+\frac{y}{x}}\right)^{5}x-o(x)$
with high probability. As a corollary, the number of disjoint fitting $PQ$
triplets in $\widehat{I}_{\sigma}$ between the indices
$((a/n)z+z^{2/3},(b/n)z-z^{2/3})$ is at least
$\frac{b-a}{n}\cdot\frac{1}{48}\left(\frac{1}{2+\frac{y}{x}}\right)^{5}x-o(x)-2z^{2/3}=\frac{b-a}{n}\cdot\frac{1}{48}\left(\frac{1}{2+\frac{y}{x}}\right)^{5}x-o(x)$
with high probability.

Combining this with the high probability event from Eq. 26

$\displaystyle X_{a}\leq a\frac{z}{n}+z^{2/3}\quad\text{and}\quad X_{b}\geq
b\frac{z}{n}-z^{2/3}$

We obtain that the number of disjoint fitting $PQ$ triplets in
$I_{\sigma}(a,b)$ is at least

$\displaystyle\frac{b-a}{n}\frac{1}{48}\left(\frac{1}{2+\frac{y}{x}}\right)^{5}x-o(x)$

with high probability, as
$(X_{a},X_{b})\supseteq((a/n)z+z^{2/3},(b/n)z-z^{2/3})$ with high probability.
∎

###  A.10 Proof of A.8

In the entire proof, we will implicitly refer to a uniform random permutation
$\sigma$ according to which the input $I$ is permuted. All the expectations
and variances will be taken over the randomness of $\sigma$. Also, let
$m=\left|\widetilde{I}\right|$.

For a given index $i\in[n]$, let $X_{i}$ be the random variable that denotes
the number of non-tiny items (i.e., of type $L/M/S$) in $I_{\sigma}(1,i)$. We
will first estimate $X_{n_{1}},X_{n_{2}}$. Let $Y_{j}$ be the indicator random
variable that denotes if the $j^{\mathrm{th}}$ item in $I_{\sigma}$ is non-
tiny. Then, $X_{i}=\sum_{j=1}^{i}Y_{j}$, and since there are $m$ non-tiny
items in total, we get

$\displaystyle\mathbb{P}\left[Y_{j}=1\right]=\frac{m}{n}\quad\text{and}\quad\mathrm{Var}\left[Y_{j}\right]=\mathbb{E}\left[Y_{j}^{2}\right]-\mathbb{E}\left[Y_{j}\right]^{2}\leq\frac{m}{n}$

Using linearity of expectations, we obtain

$\displaystyle\mathbb{E}\left[X_{i}\right]=i\frac{m}{n}$ (35)

Next, we show that $Y_{j},Y_{k}$ are negatively correlated for $j\neq k$. Note
that $\mathbb{P}\left[Y_{j}=1|Y_{k}=1\right]=\frac{m-1}{n-1}$. This is because
once the $k^{\mathrm{th}}$ position is occupied by a non-tiny item, there are
$m-1$ non-tiny items left to occupy the $j^{\mathrm{th}}$ position among the
remaining $n-1$ items. Since $\frac{m-1}{n-1}<\frac{m}{n}$, we have that
$\mathbb{P}\left[Y_{j}=1|Y_{k}=1\right]<\mathbb{P}\left[Y_{j}=1\right]$. This
implies that $\mathbb{P}\left[Y_{j}=1\land
Y_{k}=1\right]<\mathbb{P}\left[Y_{j}=1\right]\mathbb{P}\left[Y_{k}=1\right]$.
Hence,

$\displaystyle\mathrm{Cov}\left[Y_{j},Y_{k}\right]=\mathbb{E}\left[Y_{j}Y_{k}\right]-\mathbb{E}\left[Y_{j}\right]\mathbb{E}\left[Y_{k}\right]<0$

This gives us the variance bound

$\displaystyle\mathrm{Var}\left[X_{i}\right]=\sum_{j=1}^{i}\mathrm{Var}\left[Y_{j}\right]+2\sum_{1\leq
j<k\leq n}\mathrm{Cov}\left[Y_{j},Y_{k}\right]\leq i\frac{m}{n}$ (36)

Hence, using Eq. 35, Eq. 36 and Chebyshev’s inequality, we obtain

$\displaystyle\mathbb{P}\left[\left|X_{n_{1}}-\frac{m}{n}n_{1}\right|\geq
m^{2/3}\right]\leq\frac{\mathrm{Var}\left[X_{n_{1}}\right]}{m^{4/3}}\leq\frac{n_{1}(m/n)}{m^{4/3}}=O\left(\frac{1}{m^{1/3}}\right)$
$\displaystyle\mathbb{P}\left[\left|X_{n_{2}}-\frac{m}{n}n_{2}\right|\geq
m^{2/3}\right]\leq\frac{\mathrm{Var}\left[X_{n_{2}}\right]}{m^{4/3}}\leq\frac{n_{2}(m/n)}{m^{4/3}}=O\left(\frac{1}{m^{1/3}}\right)$

Hence,

$\displaystyle X_{n_{1}}\leq n_{1}\frac{m}{n}+m^{2/3}\quad\text{and}\quad
X_{n_{2}}\geq n_{2}\frac{m}{n}-m^{2/3}$ (37)

occur simultaneously with probability at least $1-O(1/m^{1/3})$. We now argue
that we have many $S$-triplets in between the above indices $n_{1},n_{2}$
using a deletion argument.

Observe that randomly shuffling $I$ and then removing all the tiny items gives
us a random permutation of $\widetilde{I}$. We group the $m$ items in
$\widetilde{I}$ into $m/3$ number of triplets as shown below.

$\displaystyle\underbrace{***}_{\mathrm{Triplet}\>T_{1}}\quad\underbrace{***}_{\mathrm{Triplet}\>T_{2}}\quad\cdots\quad\underbrace{***}_{\mathrm{Triplet}\>T_{m/3}}$

Let $n_{S}$ denote the number of small items in the input $I$ and recall that
$f_{S}$ denotes the fraction of small items in $\widetilde{I}$, i.e.,
$f_{S}=n_{S}/m$. Also, let $Z_{i}$ be the indicator random variable denoting
if the triplet $T_{i}$ is of type $SSS$ (i.e., only small items). Then,

$\mathbb{P}\left[Z_{i}=1\right]=\frac{n_{S}}{m}\cdot\frac{n_{S}-1}{m-1}\cdot\frac{n_{S}-2}{m-2}$

Now, a lower bound for the number of $S$-triplets in the time segment
$(n_{1}+1,n_{2})$ is given by the random variable
$S_{(n_{1},n_{2})}=Z_{(\frac{n_{1}}{3}+1)\frac{m}{n}}+\cdots+Z_{\frac{n_{2}}{3}\frac{m}{n}}$.
By linearity of expectations, we obtain

$\displaystyle\mathbb{E}\left[S_{(n_{1},n_{2})}\right]\geq\frac{n_{2}-n_{1}}{3}\cdot\frac{m}{n}\cdot\frac{n_{S}}{m}\cdot\frac{n_{S}-1}{m-1}\cdot\frac{n_{S}-2}{m-2}=\frac{n_{2}-n_{1}}{3n}f_{S}^{3}m-o(m)$
(38)

The above equality follows due to the fact that $f_{S}$ is a constant and $m$
is large enough; so, for all $i\in\\{0,1,2\\}$, $(n_{S}-i)/(m-i)\to f_{S}$.

We now compute $\mathrm{Var}\left[S_{(n_{1},n_{2})}\right]$ and use
Chebyshev’s inequality. For any $i$, since $Z_{i}$ is an indicator random
variable,

$\displaystyle\mathrm{Var}\left[Z_{i}\right]$
$\displaystyle=\mathbb{E}\left[Z_{i}^{2}\right]-\mathbb{E}\left[Z_{i}\right]^{2}\leq
1$

Now, consider any two triplets $T_{j},T_{k}$. We claim that the events $Z_{j}$
and $Z_{k}$ are negatively correlated. Intuitively this is clear, since if
$Z_{j}=1$, the number of small items available for placement in $T_{k}$ is
fewer. Indeed, if $Z_{j}=1$ there are $n_{S}-3$ small items available for
placement at $T_{k}$, and we have

$\displaystyle\mathbb{P}\left[Z_{k}=1|Z_{j}=1\right]$
$\displaystyle=\frac{n_{S}-3}{m-3}\cdot\frac{n_{S}-4}{m-4}\cdot\frac{n_{S}-5}{m-5}\leq\frac{n_{S}}{m}\cdot\frac{n_{S}-1}{m-1}\cdot\frac{n_{S}-2}{m-2}=\mathbb{P}\left[Z_{k}=1\right]$

Hence we obtain

$\displaystyle\mathrm{Cov}\left[Z_{j},Z_{k}\right]=\mathbb{E}\left[Z_{j}Z_{k}\right]-\mathbb{E}\left[Z_{j}\right]\mathbb{E}\left[Z_{k}\right]\leq
0$

Combining the above,

$\displaystyle\mathrm{Var}\left[S_{(n_{1},n_{2})}\right]$
$\displaystyle=\sum_{i=(n_{1}/3+1)(m/n)}^{(n_{2}/3)(m/n)}\mathrm{Var}\left[Z_{i}\right]+2\sum_{(n_{1}/3+1)(m/n)\leq
j<k\leq(n_{2}/3)(m/n)}\mathrm{Cov}\left[Z_{j},Z_{k}\right]$
$\displaystyle\leq\frac{(n_{2}-n_{1})}{3}\frac{m}{n}\leq\frac{m}{3}$ (39)

Now using Eq. 38, Section A.10 and Chebyshev’s inequality,

$\displaystyle\mathbb{P}\left[S_{(n_{1},n_{2})}\leq\mathbb{E}\left[S_{(n_{1},n_{2})}\right]-\left(\mathbb{E}\left[S_{(n_{1},n_{2})}\right]\right)^{2/3}\right]$
$\displaystyle\leq\mathbb{P}\left[\left|S_{(n_{1},n_{2})}-\mathbb{E}\left[S_{(n_{1},n_{2})}\right]\right|\geq\left(\mathbb{E}\left[S_{(n_{1},n_{2})}\right]\right)^{2/3}\right]$
$\displaystyle\leq\frac{\mathrm{Var}\left[S_{(n_{1},n_{2})}\right]}{\left(\mathbb{E}\left[S_{(n_{1},n_{2})}\right]\right)^{4/3}}$
$\displaystyle\leq O\left(\frac{m}{m^{4/3}}\right)$
$\displaystyle=O\left(\frac{1}{m^{1/3}}\right)$

This thus gives us
$S_{(n_{1},n_{2})}\geq\frac{n_{2}-n_{1}}{3n}f_{S}^{3}m-o(m)$ with high
probability.

Hence, the number of disjoint $S$-triplets in $\widetilde{I}_{\sigma}$ in the
range of indices $(n_{1}(m/n),n_{2}(m/n))$ is at least
$\frac{n_{2}-n_{1}}{3n}f_{S}^{3}m-o(m)$ with high probability. The number of
disjoint $S$-triplets in $\widetilde{I}_{\sigma}$ between the indices
$(n_{1}(m/n)+m^{2/3},n_{2}(m/n)-m^{2/3})$ is at least
$\frac{n_{2}-n_{1}}{3n}f_{S}^{3}m-o(m)-2m^{2/3}=\frac{n_{2}-n_{1}}{3n}f_{S}^{3}m-o(m)$
with high probability.

Combining this with the high probability event from Eq. 37

$\displaystyle X_{n_{1}}\leq n_{1}\frac{m}{n}+m^{2/3}\quad\text{and}\quad
X_{n_{2}}\geq n_{2}\frac{m}{n}-m^{2/3}$

we obtain that the number of disjoint $S$-triplets in
$I_{\sigma}(n_{1},n_{2})$ is at least $\frac{n_{2}-n_{1}}{3n}f_{S}^{3}m-o(m)$
with high probability, as
$(X_{n_{1}},X_{n_{2}})\supseteq(n_{1}(m/n)+m^{2/3},n_{2}(m/n)-m^{2/3})$ with
high probability.

###  A.11 Proof of A.9

The following claim will be helpful.

######  Claim A.10.

In any packing of Best-Fit, at any point of time, there cannot be two $M$-bins
both with load at most $3/4$ and both containing tiny items.

###### Proof.

Assume for the sake of contradiction that there are two $M$-bins $B_{1},B_{2}$
with tiny items satisfying $\mathrm{vol}(B_{1})\leq 3/4$ and
$\mathrm{vol}(B_{2})\leq 3/4$, where $B_{1}$ was opened before $B_{2}$. If
$B_{2}$ was opened by a tiny item, then $\mathrm{vol}(B_{1})>3/4$ at that
instant, which is a contradiction. On the other hand, if $B_{2}$ was opened by
a medium item, then $\mathrm{vol}(B_{1})>1/2$ at that instant, since medium
items have size at most $1/2$. Hence, when the first tiny item is packed in
$B_{2}$, it must be the case that $\mathrm{vol}(B_{1})>3/4$ at that instant,
which is a contradiction. ∎

Now, we will proceed to prove A.9. First, we prove that every $S$-triplet
arriving after $t^{\prime}_{\sigma}$ (with an exception of at most $O(1)$
number of them) results in the formation of a bin of weight $3/2$ (in which
future $S$-items cannot be packed) or an $SS$-bin. For each $i\in[3]$, let
$B_{i}$ be the bin where $S_{i}$ was packed. If two of the $B_{i}$-s are the
same, this would create an $SS$-bin and the lemma stands proved. Hence, from
now on, we will assume that all the $B_{i}$-s are distinct.

  * •

If any of the $B_{i}$-s is a $2$-bin before packing $S_{i}$, then after
packing $S_{i}$, it becomes a $3$-bin, thus becoming a bin of weight $3/2$ as
well as being closed for the further arriving $S$-items.

  * •

Suppose for some $i\in\\{1,2\\}$, $S_{i}$ opened a new bin or was packed into
a bin containing only tiny items. By definition of $t^{\prime}_{\sigma}$, no
tiny item appearing in between $S_{i},S_{i+1}$ can be packed on top of
$S_{i}$, or can open a new bin. So the latter case of being packed into a bin
containing only tiny items can occur at most once after $t_{\sigma}^{\prime}$,
as all bins (with at most one exception) in the packing
$\mathrm{BF}(I_{\sigma}(1,t_{\sigma}^{\prime}))$ have load greater than $3/4$.
Consequently, we consider the former case where $S_{i}$ opens a new bin. As
$S_{i+1}$ fits in $B_{i}$, it must be packed in an already existing bin.
Further, since $S_{i}$ opened a new bin, all the other bins except $B_{i}$ –
in particular, $B_{i+1}$ – must have had a load greater than $2/3$ (at the
time when $S_{i}$ arrived). Therefore, by A.4, since
$\mathrm{vol}(B_{i+1})>2/3$ before the arrival of $S_{i+1}$, we have that
$W(B_{i+1})\geq 1$ before $S_{i+1}$ arrived. Hence, after $S_{i+1}$ is packed,
since $W(S_{i+1})=0.5$, we have that $W(B_{i+1})\geq 3/2$. Also, after packing
$S_{i+1}$, no small item can be packed in $B_{i+1}$, as it has volume
$>2/3+1/4>3/4$.

  * •

Next, we consider the case when each of $S_{1},S_{2}$ is packed in a $1$-bin.
If any $B_{i}$ $(i\in\\{1,2\\})$ was an $L$-bin, then after packing $S_{i}$,
it would become a bin of weight $3/2$, and is closed to future $S$-items.
Similarly, if any $B_{i}$ $(i\in\\{1,2\\})$ was an $S$-bin, it would become an
$SS$-bin after packing $S_{i}$. The case of both $B_{1},B_{2}$ being $M$-bins
is slightly trickier. First, note that
$\mathrm{vol}(B_{1}),\mathrm{vol}(B_{2})\leq 3/4$ before the arrival of
$S_{1},S_{2}$, and that an $M$-bin with tiny items can only be created before
$t^{\prime}_{\sigma}$, since after $t_{\sigma}^{\prime}$, tiny items cannot be
added to bins with load $\leq 1/2$ or can open new bins. Moreover by A.10,
there can be at most one such $M$-bin with tiny items and load $\leq 3/4$ in
$\mathrm{BF}(I_{\sigma}(1,t_{\sigma}^{\prime}))$. Hence, this case can only
occur $O(1)$ many times.

Thus, we have established that, barring $O(1)$ number of $S$-triplets, every
other $S$-triplet results in the formation of a bin of weight $3/2$ or an
$SS$-bin. However, our aim is to prove a lower bound on the number of bins of
weight $3/2$.

Consider an $SS$-bin $B$ formed in this process. If another item of type $M/S$
is packed in the bin $B$, then it would mean that the bin $B$ has transformed
into a bin of weight $3/2$, in which case we are good. Assume otherwise, i.e.,
the bin $B$ continued to be an $SS$-bin. But, by A.3, at any point in time,
there can be at most two bins that do not contain a large item that have a
load of at most $2/3$. And by A.4, every bin with load at least $2/3$ has a
weight of at least $3/2$. Hence, every $SS$-bin (with an exception of at most
one) will get converted into a bin of weight $3/2$.

There is one final detail, however. Consider two disjoint $S$-triplets
$(S_{1},S_{2},S_{3})$ and $(S_{4},S_{5},S_{6})$. It can happen that the former
$S$-triplet resulted in an $SS$-bin $B$ and one of $S_{4},S_{5},S_{6}$ is
packed in $B$, thus creating an $SSS$-bin which has a weight of at least
$3/2$. Hence, the bins of weight $3/2$ created by both the triplets are the
same. However, when this happens, note that any of the future non-tiny
items—in particular, any of the items from the future $S$-triplets—cannot be
packed in $B$.

Therefore, if there are $\varkappa$ number of mutually disjoint $S$-triplets
after $t^{\prime}_{\sigma}$, at least $\varkappa/2-O(1)$ number of bins with
weight $3/2$ will be created after $t^{\prime}_{\sigma}$.

###  A.12 Other Omitted Proofs

###### Proof of Proposition 3.4.

We have

$\displaystyle\mathbb{P}\left[X|Y\right]$
$\displaystyle=\frac{\mathbb{P}\left[X\land
Y\right]}{\mathbb{P}\left[Y\right]}$
$\displaystyle=\frac{\mathbb{P}\left[Y\right]-\mathbb{P}\left[Y\land\overline{X}\right]}{\mathbb{P}\left[Y\right]}$
$\displaystyle\geq\frac{\mathbb{P}\left[Y\right]-\mathbb{P}\left[\overline{X}\right]}{\mathbb{P}\left[Y\right]}$
$\displaystyle=\frac{\mathbb{P}\left[Y\right]-o(1)}{\mathbb{P}\left[Y\right]}$
$\displaystyle=1-\frac{o(1)}{\mathbb{P}\left[Y\right]}$ $\displaystyle=1-o(1)$

The last inequality follows because $\mathbb{P}\left[Y\right]$ is at least a
constant. ∎

###### Proof of 3.1.

Recall from the notations section (Section 2) that when specifying the type of
a bin, we ignore the tiny items in it. By Lemma 3.2, with at most one
exception, every bin is filled to a level at least $2/3$. Consider any bin $B$
with load at least $2/3$. If $B$ is of type $L/MM/MS/SS$, then it has a weight
of at least one. If $B$ is of type $LM/LS/SSS/MSS/MMS$, then it has a weight
of at least $3/2$. Otherwise, we consider three cases depending on the
contents of $B$.

  * •

If $B$ has only tiny items, $W(B)\geq 2$ since $\mathrm{vol}(B)\geq 2/3$ and
the weight of tiny item is three times its size.

  * •

If $B$ had a medium item along with tiny items,
$W(B)\geq\frac{1}{2}+(\frac{2}{3}-\frac{1}{2})\cdot 3=1$ as a medium item has
size $\leq\frac{1}{2}$ and $B$ is at least $2/3$ full.

  * •

If $B$ had a small item along with tiny items,
$W(B)\geq\frac{1}{2}+(\frac{2}{3}-\frac{1}{3})\cdot 3=3/2$ as a small item has
size $\leq\frac{1}{3}$ and $B$ is at least $2/3$ full.

∎

###### Proof of 3.2.

The lemma follows from the following string of inequalities. Let $\mathcal{P}$
denote the packing $\mathrm{BF}(I_{\sigma}(1,t_{\sigma}))$.

$\displaystyle\mathrm{BF}(I_{\sigma}(1,t_{\sigma}))=\sum_{B\in\mathcal{P}}1$
$\displaystyle\leq\sum_{B\in\mathcal{P}}W(B)+1$ (by 3.1)
$\displaystyle=\sum_{B\in\mathcal{P}}\sum_{x\in B}W(x)+1$
$\displaystyle=\sum_{x\in I_{\sigma}(1,t_{\sigma})}W(x)+1$
$\displaystyle=W(I_{\sigma}(1,t_{\sigma}))+1$

The lemma stands proved. ∎

###### Proof of 3.3.

We first pack $\widetilde{I}_{\sigma}(1,t_{\sigma})$ in
$\mathrm{Opt}(\widetilde{I}_{\sigma}(1,t_{\sigma}))$ number of bins. Then we
pack $T(1,t_{\sigma})$ using Next-Fit [Joh73]; each bin (with only the last
bin being a possible exception) will be filled to a level greater than $3/4$.
Therefore, the total number of bins used is at most
$\mathrm{Opt}(\widetilde{I}_{\sigma}(1,t_{\sigma}))+\frac{4}{3}\mathrm{vol}(T(1,t_{\sigma}))+1$.
Thus, we have

$\displaystyle\mathrm{Opt}(I_{\sigma}(1,t_{\sigma}))$
$\displaystyle\leq\mathrm{Opt}(\widetilde{I}_{\sigma}(1,t_{\sigma}))+\frac{4}{3}\cdot
12\varepsilon\mathrm{vol}(I_{\sigma}(1,t_{\sigma}))+1$
$\displaystyle=\mathrm{Opt}(\widetilde{I}_{\sigma}(1,t_{\sigma}))+16\varepsilon\mathrm{Opt}(I_{\sigma}(1,t_{\sigma})))+1$

which gives the following lower bound on
$\mathrm{Opt}(\widetilde{I}_{\sigma}(1,t_{\sigma}))$:

$\displaystyle\mathrm{Opt}(\widetilde{I}_{\sigma}(1,t_{\sigma}))\geq\left(1-16\varepsilon\right)\mathrm{Opt}(I_{\sigma}(1,t_{\sigma}))-1$

∎

###### Proof of 3.4.

We first upper bound the weight of tiny items in the time segment
$(1,t_{\sigma})$ in terms of the weight of the non-tiny items in
$(1,t_{\sigma})$ as follows.

$\displaystyle W(T(1,t_{\sigma}))$
$\displaystyle=3\mathrm{vol}(T(1,t_{\sigma}))$ $\displaystyle\leq
3(12\varepsilon\mathrm{vol}(I_{\sigma}(1,t_{\sigma})))$
$\displaystyle=3(12\varepsilon\mathrm{vol}(\widetilde{I}_{\sigma}(1,t_{\sigma}))+12\varepsilon\mathrm{vol}(T(1,t_{\sigma})))$
$\displaystyle=3\left(12\varepsilon\mathrm{vol}(\widetilde{I}_{\sigma}(1,t_{\sigma}))+4\varepsilon
W(T(1,t_{\sigma}))\right)$

Rearranging terms, we obtain that

$\displaystyle
W(T(1,t_{\sigma}))\leq\frac{36\varepsilon}{1-12\varepsilon}\mathrm{vol}(\widetilde{I}_{\sigma}(1,t_{\sigma}))\leq\frac{36\varepsilon}{1-12\varepsilon}W(\widetilde{I}_{\sigma}(1,t_{\sigma}))$

Then,

$\displaystyle\frac{W(I_{\sigma}(1,t_{\sigma}))}{\mathrm{Opt}(I_{\sigma}(1,t_{\sigma}))}\leq\frac{W(\widetilde{I}_{\sigma}(1,t_{\sigma}))+W(T(1,t_{\sigma}))}{\mathrm{Opt}(\widetilde{I}_{\sigma}(1,t_{\sigma}))}$
$\displaystyle\leq\frac{W(\widetilde{I}_{\sigma}(1,t_{\sigma}))+\frac{36\varepsilon}{1-12\varepsilon}W(\widetilde{I}_{\sigma}(1,t_{\sigma}))}{\mathrm{Opt}(\widetilde{I}_{\sigma}(1,t_{\sigma}))}$
$\displaystyle\leq\frac{W(\widetilde{I}_{\sigma}(1,t_{\sigma}))}{\mathrm{Opt}(\widetilde{I}_{\sigma}(1,t_{\sigma}))}\left(\frac{1+24\varepsilon}{1-12\varepsilon}\right)$

∎

###### Proof of 3.5.

We lower bound $\mathrm{Opt}(\widetilde{I}_{\sigma}(1,t_{\sigma}))$ in terms
of the weight $W(\widetilde{I}_{\sigma}(1,t_{\sigma}))$ as follows

$\displaystyle
W(\widetilde{I}_{\sigma}(1,t_{\sigma}))=\sum_{B\in\mathrm{Opt}(\widetilde{I}_{\sigma}(1,t_{\sigma}))}W(B)$
$\displaystyle\leq\beta(\sigma)\mathrm{Opt}(\widetilde{I}_{\sigma}(1,t_{\sigma}))+(1-\beta(\sigma))\mathrm{Opt}(\widetilde{I}_{\sigma}(1,t_{\sigma}))\frac{3}{2}+O(1)$
$\displaystyle\leq\left(\frac{3}{2}-\frac{\beta(\sigma)}{2}\right)\mathrm{Opt}(\widetilde{I}_{\sigma}(1,t_{\sigma}))+O(1)$
(40)

Substituting Eq. 40 in 3.4, we obtain a lower bound on
$\mathrm{Opt}(I_{\sigma}(1,t_{\sigma}))$ in terms of
$W(I_{\sigma}(1,t_{\sigma})$.

$\displaystyle\frac{W(I_{\sigma}(1,t_{\sigma}))}{\mathrm{Opt}(I_{\sigma}(1,t_{\sigma}))}\leq\frac{W(\widetilde{I}_{\sigma}(1,t_{\sigma}))}{\mathrm{Opt}(\widetilde{I}_{\sigma}(1,t_{\sigma}))}\left(\frac{1+24\varepsilon}{1-12\varepsilon}\right)\leq\left(\frac{1+24\varepsilon}{1-12\varepsilon}\right)\left(\frac{3}{2}-\frac{\beta(\sigma)}{2}\right)+\frac{O(1)}{\mathrm{Opt}(\widetilde{I}_{\sigma}(1,t_{\sigma}))}$
(41)

Using 3.2, and Eq. 41, we obtain

$\displaystyle\mathrm{BF}(I_{\sigma}(1,t_{\sigma}))$ $\displaystyle\leq
W(I_{\sigma}(1,t_{\sigma}))+1$
$\displaystyle\leq\left(\frac{3}{2}-\frac{\beta(\sigma)}{2}\right)\left(\frac{1+24\varepsilon}{1-12\varepsilon}\right)\mathrm{Opt}(I_{\sigma}(1,t_{\sigma}))+\frac{O(1)\cdot\mathrm{Opt}(I_{\sigma}(1,t_{\sigma}))}{\mathrm{Opt}(\widetilde{I}_{\sigma}(1,t_{\sigma}))}+1$
$\displaystyle\leq\left(\frac{3}{2}-\frac{\beta(\sigma)}{2}\right)\left(\frac{1+24\varepsilon}{1-12\varepsilon}\right)\mathrm{Opt}(I_{\sigma}(1,t_{\sigma}))+O(1)$

where the last inequality follows from 3.3. ∎

###### Proof of 3.9.

Since $\widehat{b}$ is the number of $LM$ bins in
$\mathrm{Opt}(I^{\prime}_{\sigma}(1,t_{\sigma}))$, we have that
$\widehat{b}\leq\mathrm{Opt}(I^{\prime}_{\sigma}(1,t_{\sigma}))\leq\widehat{\ell}+\frac{\widehat{m}-\widehat{b}}{2}+1$
(from Eq. 6). Rearranging terms, we obtain
$\widehat{\ell}+\frac{\widehat{m}}{2}+1\geq\frac{3}{2}\widehat{b}$. Adding
$2\widehat{\ell}+\widehat{m}$ on both sides, we obtain

$\displaystyle
3\widehat{\ell}+\frac{3}{2}\widehat{m}+1\geq\frac{3}{2}\widehat{b}+2\widehat{\ell}+\widehat{m}$

Rearranging terms, we obtain

$\displaystyle
3\left(\widehat{\ell}+\frac{\widehat{m}-\widehat{b}}{2}\right)+1\geq
2\widehat{\ell}+\widehat{m}$ (42)

From Eq. 6, we have
$\mathrm{Opt}(I^{\prime}_{\sigma}(t_{\sigma}+1,n))\geq\widehat{\ell}+\frac{\widehat{m}-\widehat{b}}{2}$.
Hence

$\displaystyle\frac{3}{2}\mathrm{Opt}(I^{\prime}_{\sigma}(t_{\sigma}+1,n))$
$\displaystyle\geq\frac{3}{2}\left(\widehat{\ell}+\frac{\widehat{m}-\widehat{b}}{2}\right)$
$\displaystyle=\frac{3}{2}\left(\widehat{\ell}+\frac{\widehat{m}-\widehat{b}}{2}\right)$
$\displaystyle\geq\widehat{\ell}+\frac{\widehat{m}}{2}-\frac{1}{2}$ (from Eq.
42)

Multiplying both sides by $2/3$ gives us the claim. ∎

## References

  * [ADKS22] Nikhil Ayyadevara, Rajni Dabas, Arindam Khan, and K. V. N. Sreenivas.  Near-optimal algorithms for stochastic online bin packing.  In 49th International Colloquium on Automata, Languages, and Programming, ICALP 2022, July 4-8, 2022, Paris, France, 2022.
  * [AGJ23] Susanne Albers, Waldo Gálvez, and Maximilian Janke.  Machine covering in the random-order model.  Algorithmica, 85(6):1560–1585, 2023.
  * [AKL21a] Susanne Albers, Arindam Khan, and Leon Ladewig.  Best fit bin packing with random order revisited.  Algorithmica, 83(9):2833–2858, 2021.
  * [AKL21b] Susanne Albers, Arindam Khan, and Leon Ladewig.  Improved online algorithms for knapsack and GAP in the random order model.  Algorithmica, 83(6):1750–1785, 2021.
  * [BBD+18] János Balogh, József Békési, György Dósa, Leah Epstein, and Asaf Levin.  A new and improved algorithm for online bin packing.  In European Symposium on Algorithms (ESA), volume 112, pages 5:1–5:14, 2018.
  * [BBD+19] János Balogh, József Békési, György Dósa, Leah Epstein, and Asaf Levin.  A new lower bound for classic online bin packing.  In WAOA, volume 11926, pages 18–28. Springer, 2019.
  * [Car19] Carsten Oliver Fischer.  New Results on the Probabilistic Analysis of Online Bin Packing and its Variants.  PhD thesis, Rheinische Friedrich-Wilhelms-Universität Bonn, December 2019\.
  * [CJCG+13] Edward G Coffman Jr, János Csirik, Gábor Galambos, Silvano Martello, and Daniele Vigo.  Bin packing approximation algorithms: survey and classification.  In Handbook of combinatorial optimization, pages 455–531. Springer New York, 2013.
  * [CJGJ96] Edward G Coffman Jr, Michael R Garey, and David S Johnson.  Approximation Algorithms for Bin Packing: A Survey, page 46–93.  PWS Publishing Co., USA, 1996.
  * [CJJLS93] Edward G Coffman Jr, David S Johnson, George S Lueker, and Peter W Shor.  Probabilistic analysis of packing and related partitioning problems.  Statistical Science, 8(1):40–47, 1993.
  * [CJJSW93] Edward G Coffman Jr, David S Johnson, Peter W Shor, and Richard R Weber.  Markov chains, computer proofs, and average-case analysis of best fit bin packing.  In Proceedings of the twenty-fifth annual ACM symposium on theory of computing, pages 412–421, 1993.
  * [CJJSW97] Edward G Coffman Jr, David S Johnson, Peter W Shor, and Richard R Weber.  Bin packing with discrete item sizes, part ii: Tight bounds on first fit.  Random Structures & Algorithms, 10(1-2):69–101, 1997.
  * [CKPT17] Henrik I Christensen, Arindam Khan, Sebastian Pokutta, and Prasad Tetali.  Approximation and online algorithms for multidimensional bin packing: A survey.  Computer Science Review, 24:63–79, 2017.
  * [CMS93] Kenneth L Clarkson, Kurt Mehlhorn, and Raimund Seidel.  Four results on randomized incremental constructions.  Computational Geometry, 3(4):185–212, 1993.
  * [dlVL81] W Fernandez de la Vega and George S Lueker.  Bin packing can be solved within 1+epsilon in linear time.  Combinatorica, 1(4):349–355, 1981.
  * [DS14] György Dósa and J Sgall.  Optimal analysis of best fit bin packing.  In ICALP, pages 429–441, 2014.
  * [Fre83] PR Freeman.  The secretary problem and its extensions: A review.  International Statistical Review/Revue Internationale de Statistique, pages 189–206, 1983.
  * [GGJY76] Michael R Garey, Ronald L Graham, David S Johnson, and Andrew Chi-Chih Yao.  Resource constrained scheduling as generalized bin packing.  Journal of Combinatorial Theory, Series A, 21(3):257–298, 1976\.
  * [GGU72] Michael R Garey, Ronald L Graham, and Jeffrey D Ullman.  Worst-case analysis of memory allocation algorithms.  In STOC, pages 143–150, 1972.
  * [GJ78] Michael R Garey and David S Johnson.  “Strong” NP-completeness results: Motivation, examples, and implications.  J. ACM, 25(3):499–508, 1978.
  * [GKL21] Anupam Gupta, Gregory Kehne, and Roie Levin.  Random order online set cover is as easy as offline.  In 62nd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2021, Denver, CO, USA, February 7-10, 2022, pages 1253–1264. IEEE, 2021.
  * [GR20] Michel X Goemans and Thomas Rothvoss.  Polynomiality for bin packing with a constant number of item types.  J. ACM, 67(6):38:1–38:21, 2020.
  * [GS20] Anupam Gupta and Sahil Singla.  Random-order models.  In Tim Roughgarden, editor, Beyond the Worst-Case Analysis of Algorithms, pages 234–258. Cambridge University Press, 2020.
  * [Hoe63] Wassily Hoeffding.  Probability inequalities for sums of bounded random variables.  Journal of the American Statistical Association, 58(301):13–30, 1963.
  * [HR17] Rebecca Hoberg and Thomas Rothvoss.  A logarithmic additive integrality gap for bin packing.  In SODA, pages 2616–2625, 2017.
  * [JDU+74] David S Johnson, Alan Demers, Jeffrey D Ullman, Michael R Garey, and Ronald L Graham.  Worst-case performance bounds for simple one-dimensional packing algorithms.  SIAM Journal on computing, 3(4):299–325, 1974.
  * [JG85] David S Johnson and Michael R Garey.  A 71/60 theorem for bin packing.  J. Complex., 1(1):65–106, 1985.
  * [Joh73] David S Johnson.  Near-optimal bin packing algorithms.  PhD thesis, Massachusetts Institute of Technology, 1973.
  * [Ken96] Claire Kenyon.  Best-fit bin-packing with random order.  In SODA, pages 359–364, 1996.
  * [KK82] Narendra Karmarkar and Richard M Karp.  An efficient approximation scheme for the one-dimensional bin-packing problem.  In FOCS, pages 312–320, 1982.
  * [KLMS84] Richard M Karp, Michael Luby, and A Marchetti-Spaccamela.  A probabilistic analysis of multidimensional bin packing problems.  In Proceedings of the Sixteenth Annual ACM Symposium on Theory of Computing, 1984.
  * [KRTV18] Thomas Kesselheim, Klaus Radke, Andreas Tonnis, and Berthold Vocking.  Primal beats dual on online packing lps in the random-order model.  SIAM Journal on Computing, 47(5):1939–1964, 2018.
  * [LL85] Chan C Lee and Der-Tsai Lee.  A simple on-line bin-packing algorithm.  J. ACM, 32(3):562–572, July 1985.
  * [Mey01] Adam Meyerson.  Online facility location.  In Proceedings 42nd IEEE Symposium on Foundations of Computer Science, pages 426–431. IEEE, 2001.
  * [Mur88] Frank D Murgolo.  Anomalous behavior in bin packing algorithms.  Discret. Appl. Math., 21(3):229–243, 1988.
  * [MY11] Mohammad Mahdian and Qiqi Yan.  Online bipartite matching with random arrivals: an approach based on strongly factor-revealing lps.  In STOC, pages 597–606, 2011.
  * [RT93a] Wansoo T Rhee and Michel Talagrand.  On-line bin packing of items of random sizes, ii.  SIAM Journal on Computing, 22(6):1251–1256, 1993.
  * [RT93b] Wansoo T Rhee and Michel Talagrand.  On line bin packing with items of random size.  Mathematics of Operations Research, 18(2):438–445, 1993.
  * [SL94] David Simchi-Levi.  New worst-case results for the bin-packing problem.  Naval Research Logistics (NRL), 41(4):579–585, 1994.
  * [Ull71] Jeffrey D Ullman.  The performance of a memory allocation algorithm.  Technical Report, 1971.
  * [Wal12] John B Walsh.  Knowing the odds: an introduction to probability, volume 139.  American Mathematical Soc., 2012.