Indian Institute of Technology<EMAIL_ADDRESS>of
Computer Science, University of<EMAIL_ADDRESS>Department of Computer Science and Automation, Indian Institute of Science,
Bengaluru<EMAIL_ADDRESS>partly
supported by Pratiksha Trust Young Investigator Award, Google India Research
Award, and Google ExploreCS Award. Department of Computer Science and
Automation, Indian Institute of Science, Bengaluru,
<EMAIL_ADDRESS>Nikhil Ayyadevara, Rajni Dabas, Arindam Khan, and
K. V. N. Sreenivas [100]Theory of computation Design and analysis of
algorithms Online algorithms

###### Acknowledgements.

We thank Susanne Albers, Leon Ladewig, and Jirí Sgall for helpful initial
discussions. We also thank three anonymous reviewers for their comments and
suggestions.Mikołaj Bojańczyk, Emanuela Merelli, and David P. Woodruff 3 49th
International Colloquium on Automata, Languages, and Programming (ICALP 2022)
ICALP 2022 ICALP 2022 July 4–8, 2022 Paris, France 229 106

# Near-optimal Algorithms for Stochastic Online Bin Packing

Nikhil Ayyadevara∗ Rajni Dabas∗ Arindam Khan  K. V. N. Sreenivas

###### Abstract

We study the online bin packing problem under a stochastic setting. In the bin
packing problem, we are given $n$ items with sizes in $(0,1]$ and the goal is
to pack them into the minimum number of unit-sized bins. First, we study bin
packing under the i.i.d. model, where item sizes are sampled independently and
identically from a distribution in $(0,1]$. Both the distribution and the
total number of items are unknown. The items arrive one by one and their sizes
are revealed upon their arrival and they must be packed immediately and
irrevocably in bins of size $1$. We provide a simple meta-algorithm that takes
an offline $\alpha$-asymptotic approximation algorithm and provides a
polynomial-time $(\alpha+\varepsilon)$-competitive algorithm for online bin
packing under the i.i.d. model, where $\varepsilon>0$ is a small constant.
Using the AFPTAS for offline bin packing, we thus provide a linear time
$(1+\varepsilon)$-competitive algorithm for online bin packing under i.i.d.
model, thus settling the problem.

We then study the random-order model, where an adversary specifies the items,
but the order of arrival of items is drawn uniformly at random from the set of
all permutations of the items. Kenyon’s seminal result [SODA’96] showed that
the Best-Fit algorithm has a competitive ratio of at most $3/2$ in the random-
order model, and conjectured the ratio to be $\approx 1.15$. However, it has
been a long-standing open problem to break the barrier of $3/2$ even for
special cases. Recently, Albers et al. [Algorithmica’21] showed an improvement
to $5/4$ competitive ratio in the special case when all the item sizes are
greater than $1/3$. For this special case, we settle the analysis by showing
that Best-Fit has a competitive ratio of $1$. We also make further progress by
breaking the barrier of $3/2$ for the 3-Partition problem, a notoriously hard
special case of bin packing, where all item sizes lie in $(1/4,1/2]$.

###### keywords:

Bin Packing, 3-Partition Problem, Online Algorithms, Random Order Arrival, IID
model, Best-Fit Algorithm

###### category:

00footnotetext: ∗ A part of this work was done when Nikhil and Rajni were
summer interns at the Indian Institute of Science, Bengaluru. Rajni’s
internship was supported by ACM India Anveshan Setu Fellowship.

##  1 Introduction

Bin Packing (BP) is a fundamental NP-hard combinatorial optimization problem.
In BP, we are given a set of items $I:=(x_{1},x_{2},\dots,x_{n})$ with their
associated weights (also called sizes) $x_{i}$’s in $(0,1]$ and the goal is to
partition them into the minimum number of sets (bins) such that the total
weight of each set is at most 1. The problem has numerous applications in
logistics, scheduling, cutting stock, etc. [10]. Theoretically, bin packing
has been the cornerstone for approximation and online algorithms and the study
of the problem has led to the development of several interesting techniques
[31, 15, 33].

Generally, the performance guarantee of an offline (resp. online) bin packing
algorithm $\mathcal{A}$ is measured by asymptotic approximation ratio (AAR)
(resp. competitive ratio (CR)). Let $\mathrm{Opt}(I)$ and $\mathcal{A}(I)$ are
the objective values returned by the optimal (offline) algorithm and algorithm
$\mathcal{A}$, respectively, on input $I$. Then AAR (resp. CR) is defined as
$R_{\mathcal{A}}^{\infty}:=\limsup\limits_{m\rightarrow\infty}\left(\sup_{I:\mathrm{Opt}(I)=m}\frac{\mathcal{A}(I)}{\mathrm{Opt}(I)}\right)$.
Note that $R_{\mathcal{A}}^{\infty}$ focuses on instances where
$\mathrm{Opt}(I)$ is large and avoids pathological instances with large
approximation ratios where $\mathrm{Opt}(I)$ is small.

Best-Fit (BF), First-Fit (FF), and Next-Fit (NF) are the three most commonly
used algorithms for BP. Given $x_{i}$ as the present item to be packed, they
work as follows:

  * •

BF: Pack $x_{i}$ into the fullest possible bin; open a new bin if necessary.

  * •

FF: Pack $x_{i}$ into the first possible bin; open a new bin if necessary.

  * •

NF: Pack $x_{i}$ into the most recently opened bin; open a new bin if
necessary.

Johnson et al. [28] studied several heuristics for bin packing such as Best-
Fit (BF), First-Fit (FF), Best-Fit-Decreasing (BFD), First-Fit-Decreasing
(FFD) and showed their (asymptotic) approximation guarantees to be 17/10,
17/10, 11/9, 11/9, resp. Bekesi et al. [7] gave an $O(n)$ time 5/4-asymptotic
approximation algorithm. Another $O(n\log n)$ time algorithm is Modified-
First-Fit-Decreasing (MFFD) [29] which attains an AAR of $71/60\approx
1.1834$. Vega and Lueker [15] gave an asymptotic fully polynomial-time
approximation scheme (AFPTAS) for BP: For any $1/2>\varepsilon>0$, it returns
a solution with at most $(1+\varepsilon)\mathrm{Opt}(I)+O(1)$ 111In bin
packing and related problems, the accuracy parameter $\varepsilon$ is assumed
to be a constant. Here, the term $O(1)$ hides some constants depending on
$\varepsilon$. bins in time $C_{\varepsilon}+Cn\log{1/\varepsilon}$, where $C$
is an absolute constant and $C_{\varepsilon}$ depends only on $\varepsilon$.
Karmarkar and Karp [31] gave an algorithm that returns a solution using
$\mathrm{Opt}(I)+O(\log^{2}\mathrm{Opt}(I))$ bins. The present best
approximation is due to Hoberg and Rothvoss [25] which returns a solution
using $\mathrm{Opt}(I)+O(\log\mathrm{Opt}(I))$ bins.

3-Partition problem is a notoriously hard special case of BP where all item
sizes are larger than $1/4$. Eisenbrand et al. [17] mentioned that “much of
the hardness of bin packing seems to appear already in the special case of
3-Partition when all item sizes are in $(1/4,1/2]$”. This problem has deep
connections with Beck’s conjecture in discrepancy theory [45, 38]. In fact,
Rothvoss [25] conjectured that these 3-Partition instances are indeed the
hardest instances for bin packing and the additive integrality gap of the bin
packing configuration LP for these 3-Parition instances is already
$\Theta(\log n)$.

In online BP, items appear one by one and are required to be packed
immediately and irrevocably. Lee and Lee [33] presented the Harmonic algorithm
with competitive ratio $T_{\infty}\approx 1.691$, which is optimal for $O(1)$
space algorithms. For general online BP, the present best upper and lower
bounds for the CR are 1.57829 [4] and 1.54278 [5], respectively.

In this paper, we focus on online BP under a stochastic setting called the
i.i.d. model [11] where the input items are sampled from a sequence of
independent and identically distributed (i.i.d.) random variables. Here, the
performance of an algorithm is measured by the expected competitive ratio
(ECR)
$ER_{\mathcal{A}}:=\mathbb{E}[\mathcal{A}(I_{n}(F))]/\mathbb{E}[\mathrm{Opt}(I_{n}(F))]$,
where $I_{n}(F):=(X_{1},X_{2},\dots,X_{n})$ is a list of $n$ random variables
drawn i.i.d. according to some unknown distribution $F$ with support in
$(0,1]$. Mostly, bin packing has been studied under continuous uniform
(denoted by $U[a,b],0\leq a<b\leq 1$, where item sizes are chosen uniformly
from $[a,b]$) or discrete uniform distributions (denoted by $U\\{j,k\\},1\leq
j\leq k$, where item sizes are chosen uniformly from
$\\{1/k,2/k,\dots,j/k\\}$). For $U[0,1]$, Coffman et al. [13] showed that NF
has an ECR of 4/3 and Lee and Lee [34] showed that the Harmonic algorithm has
an ECR of $\pi^{2}/3-2\approx 1.2899$. Interestingly, Bentley et al. [8]
showed that the ECR of FF as well as BF converges to $1$ for $U[0,1]$. It was
later shown that the expected wasted space (i.e., the number of needed bins
minus the total size of items) is $\Theta(n^{2/3})$ for First-Fit [44, 12] and
$\Theta(\sqrt{n}\log^{3/4}n)$ for Best-Fit [44, 35]. Rhee and Talagrand [42]
exhibited an algorithm that w.h.p. achieves a packing in
$\mathrm{Opt}+O(\sqrt{n}\log^{3/4}n)$ bins for any distribution $F$ on
$(0,1]$. However, note that their competitive ratio can be quite bad when
$\mathrm{Opt}\ll n$. A distribution $F$ is said to be perfectly packable if
the expected wasted space in the optimal solution is $o(n)$ (i.e., nearly all
bins in an optimal packing are almost fully packed). Csirik et al. [14]
studied the Sum-of-Squares (SS) algorithm and showed that for any perfectly
packable distribution, the expected wasted space is $O(\sqrt{n})$. However,
for distributions that are not perfectly packable, the SS algorithm has an ECR
of at most $3$ and can have an ECR of $3/2$ in the worst-case [14]. New A
Rev.For discrete distributions? For any discrete distribution, they gave an
algorithm with an ECR of $1$ that runs in pseudo-polynomial time in
expectation. Gupta et al. [24] also obtained similar $o(n)$ expected wasted
space guarantee by using an algorithm inspired by the interior-point (primal-
dual) solution of the bin packing LP. However, it remains an open problem to
obtain a polynomial-time $(1+\varepsilon)$-competitive algorithm for online
bin packing under the i.i.d. model for arbitrary general distributions. In
fact, the present best polynomial-time algorithm for bin packing under the
i.i.d. model is BF which has an ECR of at most 3/2. However, Albers et al. [1]
showed that BF has an ECR $\geq 1.1$ even for a simple distribution: when each
item has size $1/4$ with probability $3/5$ and size $1/3$ with probability
$2/5$.

We also study the random-order model, where the adversary specifies the items,
but the arrival order is permuted uniformly at random. The performance measure
in this model is called asymptotic random order ratio (ARR):
$RR_{\mathcal{A}}^{\infty}:=\limsup\limits_{m\rightarrow\infty}\left(\sup_{I:\mathrm{Opt}(I)=m}(\mathbb{E}[\mathcal{A}(I_{\sigma})]/\mathrm{Opt}(I))\right)$.
Here, $\sigma$ is drawn uniformly at random from $\mathcal{S}_{n}$, the set of
permutations of $n$ elements, and
$I_{\sigma}:=(x_{\sigma(1)},\dots,x_{\sigma(n)})$ is the permuted list.
Random-order model generalizes the i.i.d. model [1], thus the lower bounds in
the random-order model can be obtained from the i.i.d. model. Kenyon in her
seminal paper [32] studied Best-Fit under random-order and showed that
$1.08\leq RR_{BF}^{\infty}\leq 3/2$. She conjectured that
$RR_{BF}^{\infty}\leq 1.15$. The conjecture, if true, raises the possibility
of a better alternate practical offline algorithm: first shuffle the items
randomly, then apply Best-Fit. This then beats the AAR of $71/60$ of the
present best practical algorithm MFFD. The conjecture has received a lot of
attention in the past two decades and yet, no other polynomial-time algorithm
is known with a better ARR than BF. Coffman et al. [30] showed that
$RR_{NF}^{\infty}=2$. Fischer and Röglin [21] achieved analogous results for
Worst-Fit [27] and Smart-Next-Fit [39]. Recently, Fischer [9] presented an
exponential-time algorithm, claiming an ARR of $(1+\varepsilon)$.

Monotonicity is a natural property of BP algorithms, which holds if the
algorithm never uses fewer bins to pack $\hat{I}$ when compared $I$, where
$\hat{I}$ is obtained from $I$ by increasing the item sizes. Murgolo [37]
showed that while NF is monotone, BF and FF are not.

Several other problems have been studied under the i.i.d. model and the
random-order model [16, 23, 18, 22, 19, 2, 20, 36, 24].

###  1.1 Our Contributions

Bin packing under the i.i.d. model: We achieve near-optimal performance
guarantee for the bin packing problem under the i.i.d. model, thus settling
the problem. For any arbitrary unknown distribution $F$ on $(0,1]$, we give a
meta-algorithm (see Algorithm 1) that takes an $\alpha$-asymptotic
approximation algorithm as input and provides a polynomial-time
$(\alpha+\varepsilon)$-competitive algorithm. Note that both the distribution
$F$ as well as the number of items $n$ are unknown in this case.

######  Theorem 1.1.

Let $\varepsilon\in(0,1)$ be a constant parameter. For online bin packing
under the i.i.d. model, where $n$ items are sampled from an unknown
distribution $F$, given an offline algorithm $\mathcal{A}_{\alpha}$ with an
AAR of $\alpha$ and runtime $\beta(n)$, there exists a meta-algorithm
(Algorithm 1) which returns a solution with an ECR of $(\alpha+\varepsilon)$
and runtime $O(\beta(n))$. 222As mentioned in an earlier footnote, the
$O(\cdot)$ notation hides some constants depending on $\varepsilon$ here.

Using an AFPTAS for bin packing (e.g. [15]) as $\mathcal{A}_{\alpha}$, we
obtain the following corollary.

######  Corollary 1.2.

Using an AFPTAS for bin packing as $\mathcal{A}_{\alpha}$ in Theorem 1.1, we
obtain an algorithm for online bin packing under the i.i.d. model with an ECR
of $(1+\varepsilon)$ for any $\varepsilon\in(0,1/2)$.

Most algorithms for bin packing under the i.i.d. model are based on the
following idea. Consider a sequence of $2k$ items where each item is
independently drawn from an unknown distribution $F$, and let $\mathcal{A}$ be
a packing algorithm. Pack the first $k$ items using $\mathcal{A}$; denote the
packing by $\mathcal{P}^{\prime}$. Similarly, let $\mathcal{P}^{\prime\prime}$
be the packing of the next $k$ items using $\mathcal{A}$. Since each item is
drawn independently from $F$, both $\mathcal{P}^{\prime}$ and
$\mathcal{P}^{\prime\prime}$ have the same properties in expectation; in
particular, the expected number of bins used in $\mathcal{P}^{\prime}$ and
$\mathcal{P}^{\prime\prime}$ are the same. Thus, intuitively, we want to use
the packing $\mathcal{P}^{\prime}$ as a proxy for the packing
$\mathcal{P}^{\prime\prime}$. However, there are two problems. First, we do
not know $n$, which means that there is no way to know what a good sample size
is. Second, we need to show the stronger statement that w.h.p.
$\mathcal{P}^{\prime}\approx\mathcal{P}^{\prime\prime}$. Note that the items
in $\mathcal{P}^{\prime}$ and $\mathcal{P}^{\prime\prime}$ are expected to be
similar, but they may not be the same. So, it is not clear which item in
$\mathcal{P}^{\prime}$ is to be used as a proxy for a newly arrived item in
the second half. Due to the online nature, erroneous choice of proxy items can
be quite costly. Different algorithms handle this problem in different ways.
Some algorithms exploit the properties of particular distributions, some use
exponential or pseudo-polynomial time, etc.

Rhee and Talagrand [41, 42] used upright matching to decide which item can be
considered as a proxy for a newly arrived item. They consider the model
packing $\mathcal{P}_{k}$ of the first $k$ items (let’s call these the proxy
items) using an offline algorithm. With the arrival of each of the next $k$
items, they take a proxy item at random and pack it according to the model
packing. Then, they try to fit in the real item using upright matching. They
repeat this process until the last item is packed. However, they could only
show a guarantee of $\mathrm{Opt}+O(\sqrt{n}\log^{3/4}n)$. The main drawback
of [42] is that their ECR can be quite bad if $\mathrm{Opt}\ll n$ (say,
$\mathrm{Opt}=\sqrt{n}$). One of the reasons for this drawback is that they
don’t distinguish between small and large items; when there are too many small
items, the ECR blows up.

Using a similar approach, Fischer [9] obtained a $(1+\varepsilon)$-competitive
randomized algorithm for the random-order model, but it takes exponential
time, and the analysis is quite complicated. The exponential time was crucial
in finding the optimal packing which was then used as a good proxy packing.
However, prior to our work, no polynomial-time algorithm existed which
achieves a $(1+\varepsilon)$ competitive ratio.

To circumvent these issues, we treat large and small items separately.
However, a straightforward adaptation faces several technical obstacles. Thus
our analysis required intricate applications of concentration inequalities and
sophisticated use of upright matching. First, we consider the semi-random case
when we know $n$. Our algorithm works in stages. For a small constant
$\delta\in(0,1]$, the first stage contains only $\delta^{2}n$ items. These
items give us an estimate of the distribution. If the packing does not contain
too many large items, we show that the simple Next-Fit algorithm suffices for
the entire input. Otherwise, we use a proxy packing of the set of first
$\delta^{2}n$ items to pack the next $\delta^{2}n$ items. In the process, we
pack the small and large items differently. Then we use the proxy packing of
the first $2\delta^{2}n$ items to pack the next $2\delta^{2}n$ items and so
on. In general, we use the proxy packing of the first $2^{i}\delta^{2}n$ items
to pack the next $2^{i}\delta^{2}n$ items.

Finally, we get rid of the assumption that we know $n$ using a doubling trick
(we guess $n$ first and keep doubling the guess if it turns out to be
incorrect). However, there are several difficulties (e.g. input stopping
midway of two consecutive guesses, large wasted space in the past stages).
Yet, with involved technical adaptations, we can handle them (see Section 2.2
and Section A.5).

Our algorithm is simple, polynomial-time (in fact, $O(n)$ time), and achieves
essentially the best possible competitive ratio. It is relatively simpler to
analyze when compared to Fischer’s algorithm [9]. Also, unlike the algorithms
of Rhee and Talagrand [42] as well as Fischer [9], our algorithm is
deterministic. This is because, unlike their algorithms, instead of taking
proxy items at random, we pack all the proxy items before the start of a stage
and try to fit in the real items as they come. This makes our algorithm
deterministic. Our algorithm is explained in detail in Section 2.1. The nature
of the meta-algorithm provides flexibility and ease of application. See Table
1 for the performance guarantees obtained using different offline algorithms.

See Section 2 for the details of the proof and the description of our
algorithm. In fact, our algorithm can easily be generalized to $d$-dimensional
online vector packing [6], a multidimensional generalization of bin packing.
See Section C in the Appendix for a $d(\alpha+\varepsilon)$ competitive
algorithm for $d$-dimensional online vector packing where the
$i^{\mathrm{th}}$ item $X_{i}$ can be seen as a tuple
$\left(X_{i}^{(1)},X_{i}^{(2)},\dots,X_{i}^{(d)}\right)$ where each
$X_{i}^{(j)}$ is independently sampled from an unknown distribution
$\mathcal{D}^{(j)}$.

Bin packing under the random-order model: Next, we study BP under the random-
order model. Recently, Albers et al. [1] showed that BF is monotone if all the
item sizes are greater than 1/3. Using this result, they showed that in this
special case, BF has an ARR of at most $5/4$. We show that, somewhat
surprisingly, in this case, BF actually has an ARR of 1 (see Section 3.1 for
the detailed proof).

######  Theorem 1.3.

For online bin packing under the random-order model, Best-Fit achieves an
asymptotic random-order ratio of $1$ when all the item sizes are in $(1/3,1]$.

Next, we study the $3$-partition problem, a special case of bin packing when
all the item sizes are in $(1/4,1/2]$. This is known to be an extremely hard
case [25]. Albers et al. [1] mentioned that “it is sufficient to have one item
in $(1/4,1/3]$ to force Best-Fit into anomalous behavior.” E.g., BF is non-
monotone in the presence of items of size less than $1/3$. Thus the techniques
of [1] do not extend to the 3-Partition problem. We break the barrier of $3/2$
in this special case, by showing that BF attains an ARR of $\approx 1.4941$.

######  Theorem 1.4.

For online bin packing under the random-order model, Best-Fit achieves an
asymptotic random-order ratio of $\approx 1.4941$ when all the item sizes are
in $(1/4,1/2]$.

We prove Theorem 1.4 in Section 3.2. As 3-partition instances are believed to
be the hardest instances for bin packing, our result gives a strong indication
that the ARR of BF might be strictly less than $3/2$.

$\mathcal{A}_{\alpha}$ | Time Complexity | Expected Competitive Ratio
---|---|---
AFPTAS [15] | $O(C_{\varepsilon}+Cn\log{1/\varepsilon})$ | $(1+\varepsilon)$
Modified-First-Fit-Decreasing [29] | $O(n\log n)$ | $(71/60+\varepsilon)$
Best-Fit-Decreasing [26] | $O(n\log n)$ | $({11}/{9}+\varepsilon)$
First-Fit-Decreasing [26] | $O(n\log n)$ | $({11}/{9}+\varepsilon)$
Next-Fit-Decreasing [3] | $O(n\log n)$ | $(T_{\infty}+\varepsilon)$
Harmonic [33] | $O(n)$ | $(T_{\infty}+\varepsilon)$
Next-Fit | $O(n)$ | $(2+\varepsilon)$
Table 1: Analysis of Algorithm 1 depending on $\mathcal{A}_{\alpha}$. In the
first row, $C$ is an absolute constant and $C_{\varepsilon}$ is a constant
that depends on $\varepsilon$.

##  2 Online Bin Packing Problem under the i.i.d. Model

In this section, we provide the meta algorithm as described in Theorem 1.1.
For the ease of presentation, we split this into two parts. In Section 2.1, we
assume a semi-random model, i.e., we assume that the number of items $n$ is
known beforehand and design an algorithm. Later, in Section 2.2, we get rid of
this assumption.

Let the underlying distribution be $F$. Without loss of generality, we assume
that the support set of $F$ is a subset of $(0,1]$. For any set of items $J$,
we define $\mathcal{W}(J)$ as the sum of weights of all the items in $J$. For
any $k\in\mathbb{N}_{+}$, we denote the set $\\{1,2,\dots,k\\}$ by $[k]$. Let
$\varepsilon\in(0,1)$ be a constant parameter and let $0<\delta<\varepsilon/8$
be a constant. Let $\mathcal{A}_{\alpha}$ be an offline algorithm for bin
packing with an AAR of $\alpha>1$ and let $\mathrm{Opt}$ denote the optimal
algorithm. For any $i\in[n]$, we call $x_{i}$ to be a _large_ item if
$x_{i}\geq\delta$ and a _small_ item otherwise. Let $I_{\ell}$ and $I_{s}$
denote the set of large and small items in $I$, respectively.

###  2.1 Algorithm Assuming that the Value of $n$ is Known

We now describe our algorithm which assumes the knowledge of the number of
items. For simplicity, in this section we assume both $n$ and $1/\delta^{2}$
to be powers of 2. Otherwise, we can round down
$\delta\in[1/2^{i+1},1/2^{i}),i\in\mathbb{N}$ to $1/2^{i+1}$. Also, we will
anyway get rid of the assumption on the knowledge of $n$ in the next
subsection, and there we do not need $n$ to be a power of 2. We denote this
algorithm by $\mathtt{Alg}$. First, we give a high level idea of the
algorithm. We divide the entire input into stages as follows: we partition the
input set $I$ into $m:=\left({\log(1/\delta^{2})}+1\right)$ stages
$T_{0},T_{1},\dots,T_{m-1}$. The zeroth stage $T_{0}$, called the _sampling
stage_ , contains the first $\delta^{2}n$ items, i.e.,
$x_{1},x_{2},\dots,x_{\delta^{2}n}$. For $j\in[m-1]$, $T_{j}$ contains the
items with index starting from $2^{j-1}\delta^{2}n+1$ till $2^{j}\delta^{2}n$.
In essence, $T_{0}$ contains the first $\delta^{2}n$ items, $T_{1}$ contains
the next $\delta^{2}n$ items, $T_{2}$ contains the next $2\delta^{2}n$ items,
and so on. Note that the number of stages $m$ is a constant. In any stage
$T_{j}$, we denote the set of large items and small items by $L_{j}$ and
$S_{j}$, respectively. For $j\in[m-1]$, let $\overline{T_{j}}$ denote the set
of items which have arrived before the stage $T_{j}$, i.e.,
$\overline{T_{j}}=T_{0}\cup T_{1}\cup\dots\cup T_{j-1}$. Similarly, we define
$\overline{L_{j}}$ and $\overline{S_{j}}$ as the set of large items and small
items, respectively, in $\overline{T_{j}}$. Note that for any $j\in[m-1]$,
$\left|T_{j}\right|=\left|\overline{T_{j}}\right|$ and since all the items are
sampled independently from the same distribution, we know that with high
probability, the optimal solutions of $T_{j}$ and $\overline{T_{j}}$ are quite
similar. Since $\overline{T_{j}}$ would have arrived before $T_{j}$, we
compute an almost optimal packing of $\overline{T_{j}}$ (in an offline manner)
and use it as a blueprint to pack $T_{j}$.

The algorithm is as follows: first, we pack $T_{0}$, the sampling stage using
Next-Fit. The sampling stage contains only a small but a constant fraction of
the entire input set; hence it uses only a few number of bins when compared to
the final packing but at the same time provides a good estimate of the
underlying distribution. If the number of large items in the sampling stage is
at most $\delta^{3}\mathcal{W}(T_{0})$, then we continue using Next-Fit for
the rest of the entire input too. Intuitively, NF performs well in this case
as most of the items are small. Thus, from now on, let us assume otherwise.
Now assume that we are at an intermediate point where $\overline{T_{j}}$ has
arrived and $T_{j}$ is about to arrive ($j\geq 1$). We create $D_{j}$, the set
of _proxy_ items, which is just a copy of $\overline{T_{j}}$. We pack $D_{j}$
using $\mathcal{A}_{\alpha}$. Let this packing be denoted by
$\mathcal{P}_{j}$. Let $B_{j}^{(k)}$ denote the $k^{\mathrm{th}}$ bin in the
packing $\mathcal{P}_{j}$. We iterate over $k$ and remove all the small items
in the bin $B_{j}^{(k)}$ and create a slot in the free space of $B_{j}^{(k)}$.
We call this slot to be an _$S$ -slot_. When an item $x_{i}\in T_{j}$ arrives,
we check if $x_{i}$ is small or large

  * •

If $x_{i}$ is small, we pack it in one of the $S$-slots greedily, using Next-
Fit. If it doesn’t fit in any of the $S$-slots, then we create a new bin with
only one $S$-slot spanning the entire bin (so, this bin will only be used to
pack small items), and pack it there.

  * •

If $x_{i}$ is large, we remove the smallest proxy item with a size more than
$x_{i}$ in the packing $\mathcal{P}_{j}$ and pack it there. If no such proxy
item exists, we open a new bin, pack $x_{i}$ in there and close it, meaning
that it will not be used to pack any further items.

After $T_{j}$ is packed completely, we just discard the proxy items in the
packing that haven’t been replaced and move to the next stage. For more formal
details and pseudocode for the algorithm, please refer to Algorithm 1.

Algorithm 1 $\mathtt{Alg}(x_{1},x_{2},\dots,x_{n})$: A nearly optimal
algorithm for online bin packing assuming that the number of items $n$ is
known before-hand

1:Input: $I_{n}(\mathcal{D})=\\{x_{1},x_{2},...,x_{n}\\}$.

2:for $i$= $1$ to $\delta^{2}n$ do$\triangleright$ Sampling Stage, $T_{0}$

3: Pack $x_{i}$ using $\mathrm{NF}$.

4:end for

5:if $\left|L_{0}\right|\leq\delta^{3}\mathcal{W}(T_{0})$ then
$\triangleright$ Very few large items

6: Use $\mathrm{NF}$ for all remaining stages.

7:else

8: for $j$= $1$ to $m-1$ do

9: $D_{j}\leftarrow\overline{T_{j}};L(D_{j})\leftarrow$ set of large items in
$D_{j}$.

10: Pack $D_{j}$ using $\mathcal{A}_{\alpha}$.

11: Let the packing be denoted by $\mathcal{P}_{j}$. $\triangleright$ Packing
of proxy items

12: $\mathcal{S}_{j}\leftarrow\phi$. $\triangleright$ the set of $S$-slots

13: for bin $B$ in $\mathcal{P}_{j}$ do

14: Remove the small items in $B$.

15: Create an $S$-slot $H$ of size equal to ($1-$weight of all the large items
in $B$).

16: $\mathcal{S}_{j}\leftarrow\mathcal{S}_{j}\cup H$.

17: end for

18: for $x_{i}\in T_{j}$ do

19: if $x_{i}$ is large then

20: if $\exists d\in L(D_{j})$ such that $d\geq x_{i}$ then

21: Find smallest such $d$.

22: $L(D_{j})\leftarrow L(D_{j})\setminus\\{d\\}$.

23: Pack $x_{i}$ in place of $d$ in the packing $\mathcal{P}_{j}$.

24: else

25: Open a new bin and pack $x_{i}$ and close the bin.

26: end if

27: else

28: Try packing $x_{i}$ in $\mathcal{S}_{j}$ using Next-Fit.

29: if $x_{i}$ couldn’t be packed then

30: Open a new bin $B^{\prime}$ with a single $S$-slot of unit capacity.

31: $\mathcal{S}_{j}\leftarrow\mathcal{S}_{j}\cup B^{\prime}$.

32: Pack $x_{i}$ in $B^{\prime}$.

33: end if

34: end if

35: end for

36: end for

37:end if

We will proceed to analyze the algorithm. But first, we will discuss
stochastic upright matching and a standard result on it. Using a standard
probabilistic concentration lemma, we will formulate a few lemmas which are
going to be very important for the analysis of the algorithm.

Stochastic Upright Matching. Rhee and Talagrand [43] studied stochastic
upright matching problem in the context of analysis of bin packing algorithms.
Consider a set $P=\\{(x_{i},y_{i})\\}_{i\in[2n]}$ of $2n$ points where each
$x_{i}$ is either $+1$ or $-1$ with equal probability and
$y_{1},y_{2},\dots,y_{2n}$ are sampled according to an i.i.d. distribution. We
can define a bipartite graph $\mathcal{G}$ as follows: the vertex set is $P$,
viewed as a set of points in $\mathbb{R}\times\mathbb{R}$. Two points
$P_{1}=(x_{1},y_{1}),P_{2}=(x_{2},y_{2})$ share an edge iff $x_{1}=1,x_{2}=-1$
and $y_{1}\geq y_{2}$.

The objective of the problem is to find a maximum matching in $\mathcal{G}$
or, in other words, minimize the number of unmatched points which we denote by
$U(P)$. We denote this matching variant by $\mathcal{M}$. The following lemma
shows that w.h.p., the number of unmatched points is $O(\sqrt{n}(\log
n)^{3/4})$. The proof of the lemma follows from Lemma 3.1 in [43].

######  Lemma 2.1.

[43] Let ${P}$ be an instance for $\mathcal{M}$. Then there exist constants
$a,C,K>0$ such that,

Concentration Inequalities. Now we state the concentration inequalities.

######  Lemma 2.2 (Bernstein’s Inequality).

Let $X_{1},X_{2},\dots,X_{n}$ be independent random variables such that each
$X_{i}\in[0,1]$. Then, for any $\lambda>0$, the following inequality holds.

The following lemma is a direct implication of the results of [42, 40].

######  Lemma 2.3.

For any $t\in[n]$, let $I(1,t)$ denote the first $t$ items of the input set
$I$. Then there exist constants $K,a>0$ such that,

The following lemmas are about how a property of a part of the input (say, the
total size) compares to that of the entire input.

######  Lemma 2.4.

For an input set $I$ of $n$ items drawn from a distribution independently, for
any arbitrary set $J\subseteq I$ we have,

######  Lemma 2.5.

Let $I$ be an input set of $n$ items drawn from a distribution independently
and let $J$ be any subset of $I$. Suppose $J_{\ell}$ (resp. $I_{\ell}$) denote
the set of large items in $J$ (resp. $I$). Then we have,

######  Lemma 2.6.

For any $t\in\\{1,2,\ldots,n\\}$, Suppose $I(1,t)$ denote the first $t$ items
of the input set $I$. Then there exist constants $C,a>0$ such that with
probability at least
$1-\exp\left(-a\left(\log\mathbb{E}\left[\mathrm{Opt}(I)\right]\right)^{1/3}\right)$,
we have
$\mathrm{Opt}(I(1,t))\leq(1+2\delta)\frac{t}{n}\mathbb{E}\left[\mathrm{Opt}(I)\right]+C\mathbb{E}\left[\mathrm{Opt}(I)\right]^{2/3}.$

Lemma 2.3 (resp. Lemmas 2.4 and 2.5) intuitively states that the optimal
solution for (resp. the weight of the items of, and the number of large items
in) a part of the input is almost a linear function of the length of the part.
This makes sense because each item comes from the same distribution. Lemma 2.6
further tries to improve on Lemma 2.3 by bounding the lower order terms in
terms of $\mathbb{E}\left[\mathrm{Opt}(I)\right]$ instead of $n$ while losing
only a small factor of $1+2\delta$. This is crucial since we need to bound the
number of additional bins used by our algorithm in terms of
$\mathbb{E}\left[\mathrm{Opt}(I)\right]$ and not in terms of $n$. We give the
proofs of Lemmas 2.3, 2.4, 2.5 and 2.6 in Appendix A. As mentioned, Lemma 2.3
follows from [42, 40]. Lemmas 2.4 and 2.5 are simple applications of
Bernstein’s inequality. The high-level proof of Lemma 2.6 goes as follows:
first we consider the optimal packing of the large items in $I(1,t)$, then we
pack the small items in $I(1,t)$ greedily. If the small items open new bins
then it means that all the bins (except one) are filled up to a level at least
$1-\delta$. Otherwise, we don’t use any extra bins. So,
$\mathrm{Opt}(I(1,t))\leq\max\\{\mathrm{Opt}(I_{\ell}(1,t)),(1+2\delta)\mathcal{W}(I(1,t))+1\\}$.
Then we use Lemmas 2.3, 2.4 and 2.5 to prove Lemma 2.6.

With these helpful lemmas, we now proceed to analyze the algorithm. We split
the analysis into the following two cases: when
$\left|L_{0}\right|\leq\delta^{3}\cdot\mathcal{W}(T_{0})$ and when
$\left|L_{0}\right|>\delta^{3}\cdot\mathcal{W}(T_{0})$.

####  2.1.1 Case 1: $\left|L_{0}\right|\leq\delta^{3}\cdot\mathcal{W}(T_{0})$

Recall that in this case, we just continue with Next-Fit for all the remaining
items. To bound the Next-Fit solution, we first consider the number of bins
that contain at least one large item. For this, we bound the value of
$\left|I_{\ell}\right|$. Then we consider the bins that contain only small
items and bound this value in terms of weight of all items $\mathcal{W}(I)$.

######  Claim 6.

Let $K:=\mathbb{E}\left[\mathrm{Opt}(I)\right]$. For some positive constants
$C_{1},C_{2},a$, we have that

######  Proof 2.7.

As the sampling stage contains $\delta^{2}n$ items,
$\mathbb{E}\left[\left|L_{0}\right|\right]=\delta^{2}\mathbb{E}\left[\left|I_{\ell}\right|\right]$.
From Lemma 2.5, we have , and
From the above inequalities we have,
$\left|I_{\ell}\right|\leq\frac{1}{\delta^{2}}\left|L_{0}\right|+\left(1+\frac{1}{\delta^{2}}\right)\mathbb{E}\left[\mathcal{W}(I)\right]^{2/3}$
with probability at least
$1-4\exp\left(-\frac{\delta}{3}\mathbb{E}\left[\mathcal{W}(I)\right]^{1/3}\right)$.
We can use the inequalities
$\mathbb{E}\left[\mathrm{Opt}(I)\right]\geq\mathbb{E}\left[\mathcal{W}(I)\right]$
and $\left|L_{0}\right|\leq\delta^{3}\cdot\mathcal{W}(T_{0})$ to conclude the
proof of this claim.

Now we bound the number of bins that are closed by small items. Note that
Next-Fit fills each such bin up to a capacity at least $(1-\delta)$. So, the
number of such bins is at most $\frac{1}{1-\delta}\mathcal{W}(I)$ when all
items are packed by Next-Fit. Also, there can be at most one bin that can be
open. Thus combining all these results, (and using inequality
$\frac{1}{1-\delta}\leq 1+2\delta$ for $\delta<\frac{1}{2}$) with high
probability,
$\mathrm{NF}(I)\leq\left|I_{\ell}\right|+(1+2\delta)\mathcal{W}(I)+1\leq\delta\cdot\mathcal{W}(T_{0})+(1+2\delta)\mathcal{W}(I)+K\mathbb{E}\left[\mathrm{Opt}(I)\right]^{2/3}\text{,
for some constant $K$.}$

Using Lemma 2.4, we get that with high probability,
$\mathcal{W}(I)\leq\mathbb{E}\left[\mathcal{W}(I)\right]+\mathbb{E}\left[\mathcal{W}(I)\right]^{2/3}$.
Using the facts $\mathcal{W}(I)\geq\mathcal{W}(T_{0})$ and
$\mathbb{E}\left[\mathrm{Opt}(I)\right]/2\leq\mathbb{E}\left[\mathcal{W}(I)\right]\leq\mathbb{E}\left[\mathrm{Opt}(I)\right]$,
we get,

$\displaystyle\mathrm{NF}(I)\leq(1+3\delta)\mathbb{E}\left[\mathrm{Opt}(I)\right]+C_{3}\mathbb{E}\left[\mathrm{Opt}(I)\right]^{2/3}$
(1)

with probability of at least
$1-C_{4}\exp\left(-a_{1}\mathbb{E}\left[\mathrm{Opt}(I)\right]^{1/3}\right)$
for some constants $C_{3},C_{4},a_{1}>0$. When the low probability event
occurs, we can use the upper bound of $\mathrm{NF}(I)\leq 2\mathrm{Opt}(I)-1$
to obtain the competitive ratio. Let
$p=C_{4}\exp\left(-a_{1}\mathbb{E}\left[\mathrm{Opt}(I)\right]^{1/3}\right)$.

$\displaystyle\mathbb{E}\left[\mathrm{NF}(I)\right]$
$\displaystyle\leq(1-p)\left((1+3\delta)\mathbb{E}\left[\mathrm{Opt}(I)\right]+K\mathbb{E}\left[\mathrm{Opt}(I)\right]^{2/3}+1\right)+p(2\mathbb{E}\left[\mathrm{Opt}(I)\right]-1)$
$\displaystyle=(1+3\delta+2p)\mathbb{E}\left[\mathrm{Opt}(I)\right]+o(\mathbb{E}\left[\mathrm{Opt}(I)\right])$

Since $p=o(1)$ when $\mathbb{E}\left[\mathrm{Opt}(I)\right]$ tends to
infinity, we obtain that the expected competitive ratio tends to at most
$1+3\delta<1+\varepsilon$.

####  2.1.2 Case 2: $\left|L_{0}\right|>\delta^{3}\cdot\mathcal{W}(T_{0})$

We split our analysis in this case into two parts. We first analyze the number
of bins used in the sampling stage $T_{0}$ and then analyze the number of bins
used in the remaining stages.

Using Lemma 2.5, we obtain w.h.p. that
$\left|L_{0}\right|\leq\delta^{2}\mathbb{E}\left[\left|I_{\ell}\right|\right]+\mathbb{E}\left[\mathcal{W}(I)\right]^{2/3}$.
Hence,

$\displaystyle\mathbb{E}\left[\left|I_{\ell}\right|\right]$
$\displaystyle\geq\frac{1}{\delta^{2}}\left|L_{0}\right|-\frac{1}{\delta^{2}}\mathbb{E}\left[\mathcal{W}(I)\right]^{2/3}$
$\displaystyle\geq\delta\mathcal{W}(T_{0})-\frac{1}{\delta^{2}}\mathbb{E}\left[\mathcal{W}(I)\right]^{2/3}$
(since $\left|L_{0}\right|>\delta^{3}\cdot\mathcal{W}(T_{0})$)
$\displaystyle\geq\delta^{3}\mathbb{E}\left[\mathcal{W}(I)\right]-{\left(\delta+\frac{1}{\delta^{2}}\right)}\mathbb{E}\left[\mathcal{W}(I)\right]^{2/3}$
(2)

The last inequality follows from Lemma 2.4. For any $j\geq 1$, using
${\left|T_{j}\right|}/{n}\geq\delta^{2}$ and using Lemma 2.5, we get,

$\displaystyle\left|L_{j}\right|\geq\delta^{5}\mathbb{E}\left[\mathcal{W}(I)\right]-{({2+\delta^{3}})}\mathbb{E}\left[\mathcal{W}(I)\right]^{2/3}$
(3)

Each of the Eqs. (2),(3) holds with a probability of at least
$1-C\exp\left(-a\mathbb{E}\left[\mathcal{W}(I)\right]^{1/3}\right)$ for some
constants $C,a>0$.

Note that $\mathcal{W}(I)\geq\mathrm{Opt}(I)/2$. So from now on we assume that
there exist constants $C_{1},C_{2}>0$ which depend on $\delta$ such that
w.h.p. both the following inequalities hold.

$\displaystyle\mathbb{E}\left[\left|I_{\ell}\right|\right]$ $\displaystyle\geq
C_{1}\cdot\mathbb{E}\left[\mathrm{Opt}(I)\right]$ (4)
$\displaystyle\left|L_{j}\right|$ $\displaystyle\geq
C_{2}\cdot\mathbb{E}\left[\mathrm{Opt}(I)\right]$ (5)

  * •

Analysis of the Sampling Stage: Recall that the number of items considered in
the sampling phase is $\delta^{2}n$. We will bound the number of large items
and the weight of items in this stage using Bernstein’s inequality.

    1. 1.

Since sampling phase has $\delta^{2}n$ items,
$\mathbb{E}\left[\left|L_{0}\right|\right]=\delta^{2}\mathbb{E}\left[\left|I_{\ell}\right|\right]$.
By applying Bernstein’s inequality for
$X_{1},X_{2},\dots,X_{\left|T_{0}\right|}$ where $X_{i}$ takes value $1$ is
$x_{i}$ is large and $0$ otherwise, we get,

$\displaystyle=$ $\displaystyle\leq
2\exp\left(-\frac{\delta^{4}\mathbb{E}\left[\left|I_{\ell}\right|\right]^{2}}{2\mathbb{E}\left[{\left|L_{0}\right|}\right]+\frac{2}{3}\delta^{2}\mathbb{E}\left[\left|I_{\ell}\right|\right]}\right)\leq
2\exp\left(-\frac{1}{3}\delta^{2}\mathbb{E}\left[\left|I_{\ell}\right|\right]\right)$
$\displaystyle\leq
2\exp\left(-a_{1}\cdot\mathbb{E}\left[\mathrm{Opt}(I)\right]\right)$ (from
Equation 4)

for some constant $a_{1}>0$. So, with high probability,
$\left|L_{0}\right|\leq
2\delta^{2}\mathbb{E}\left[\left|I_{\ell}\right|\right]\leq
2\delta\mathbb{E}\left[\mathrm{Opt}(I)\right]$.

    2. 2.

Similarly,
$\mathbb{E}\left[\mathcal{W}(T_{0})\right]=\delta^{2}\mathbb{E}\left[\mathcal{W}(I)\right]$.
By applying Bernstein’s inequality for
$X_{1},X_{2},\dots,X_{\left|T_{0}\right|}$ where $X_{i}$ takes value $x_{i}$,
we get,

$\displaystyle=$ $\displaystyle\leq
2\exp\left(\frac{-\delta^{4}\mathbb{E}\left[\mathcal{W}(I)\right]^{2}}{2\delta^{2}\mathbb{E}\left[{\mathcal{W}(T_{0})}\right]+\frac{2}{3}\delta^{2}\mathbb{E}\left[\mathcal{W}(I)\right]}\right)$
$\displaystyle\leq
2\exp\left(\frac{-\delta^{2}}{3}\mathbb{E}\left[\mathcal{W}(I)\right]\right)\leq
2\exp\left(\frac{-\delta^{2}\mathbb{E}\left[\mathrm{Opt}(I)\right]}{6}\right)$

So, with high probability we have, $\mathcal{W}(T_{0})\leq
2\delta^{2}\mathbb{E}\left[\mathcal{W}(I)\right]{\leq
2\delta^{2}\mathbb{E}\left[\mathrm{Opt}(I)\right]}$.

Since the number of bins opened by Next-Fit $\mathrm{NF}(T_{0})$ is at most
$\left|L_{0}\right|+\frac{1}{1-\delta}\mathcal{W}(T_{0})+1$, using the bounds
on the number of large items and weight of small items in sampling phase,
w.h.p. we have,

$\displaystyle\mathrm{NF}(T_{0})\leq
2\delta\mathbb{E}\left[\mathrm{Opt}(I)\right]+\frac{2\delta^{2}}{1-\delta}\mathbb{E}\left[{\mathrm{Opt}(I)}\right]\leq
4\delta\mathbb{E}\left[\mathrm{Opt}(I)\right]$ (6)

  * •

Analysis of the Remaining Stages: Consider any stage $T_{j}$ $(j>0)$ after the
sampling stage. Note that $\left|\overline{T_{j}}\right|=\left|T_{j}\right|$.
A bin can be opened in three different ways.

    1. 1.

When a new bin is opened while packing the set of proxy items $D_{j}$ using
$\mathcal{A}_{\alpha}$ (see the algorithm description in Section 2.1).

    2. 2.

When a large item can’t replace a proxy item and hence a new bin is opened for
it.

    3. 3.

When a small item can’t fit in the set of $S$-slots and hence a new bin is
opened with a single $S$-slot spanning the entire bin.

In our analysis, first we bound the number of bins opened by
$\mathcal{A}_{\alpha}$ for proxy items; we use Lemma 2.6 to obtain this bound.
Then we show that the number of large items which cannot replace a proxy item
would be very small by using upright matching arguments (Lemma 2.1). For small
items, we bound the number of new bins opened by using the fact that
$\mathcal{W}(S_{j})$ and $\mathcal{W}(\overline{S_{j}})$ are very close which
will be proved using Bernstein’s inequality.

Now we analyze the number of bins opened in the first way (say
$A_{\mathrm{proxy}}^{j}$). This is nothing but the number of bins opened by
$\mathcal{A}_{\alpha}$ to pack $\overline{T_{j}}$. Since,
$\mathcal{A}_{\alpha}$ has an AAR of $\alpha$, by using Lemma 2.6, we have,

$\displaystyle A_{\mathrm{proxy}}^{j}=\mathcal{A}_{\alpha}(\overline{T_{j}})$
$\displaystyle\leq\alpha\mathrm{Opt}(\overline{T_{j}})+o(\mathrm{Opt}(\overline{T_{j}}))$
$\displaystyle\leq\alpha(1+2\delta)({\left|\overline{T_{j}}\right|}/{n})\mathbb{E}\left[\mathrm{Opt}(I)\right]+C_{3}\mathbb{E}\left[\mathrm{Opt}(I)\right]^{2/3}+o(\mathrm{Opt}(I))$
(7)

with probability at least
$1-\exp\left(-a_{2}\log(\mathbb{E}\left[\mathrm{Opt}(I)\right])^{1/3}\right)$,
for some constants $C_{3},a_{2}>0$.

We now bound the number of bins opened in the second way. Using Lemma 2.5, we
get that w.h.p.,
$\left|\overline{L_{j}}\right|\geq\frac{\left|\overline{T_{j}}\right|}{n}\mathbb{E}\left[\left|I_{\ell}\right|\right]-\mathbb{E}\left[\mathcal{W}(I)\right]^{2/3}$,
and
$\left|L_{j}\right|\leq\frac{\left|T_{j}\right|}{n}\mathbb{E}\left[\left|I_{\ell}\right|\right]+\mathbb{E}\left[\mathcal{W}(I)\right]^{2/3}$.
Since $\left|\overline{T_{j}}\right|=\left|T_{j}\right|$ we have,

$\left|L_{j}\right|\leq\left|\overline{L_{j}}\right|+2\mathbb{E}\left[\mathcal{W}(I)\right]^{2/3}.$
(8)

So, w.h.p. the number of large items in $T_{j}$ doesn’t exceed that of those
in $\overline{T_{j}}$ by a large number. Now consider the number of bins
opened because there is no feasible proxy item that can be replaced. Let this
number be $A_{\mathrm{unmatch}}^{j}$. We can interpret this number as the
number of unmatched items when we use the stochastic matching variant
$\mathcal{M}$ from [43] as follows. We can interpret each item
$\overline{t}\in\overline{L_{j}}$ as a point
$P_{\overline{t}}:=(+1,\overline{t})$ and each point $t\in L_{j}$ as a point
$P_{t}:=(-1,t)$. For simplicity, let’s call the points with $+1$ as their
first coordinate as _plus_ points and the points with $-1$ as their first
coordinate as _minus_ points. We match a point $P_{\overline{t}}$ with $P_{t}$
iff $t$ replaced $\overline{t}$ in our algorithm. It is shown in [44] that
such matching is always maximum. Hence the number of items that open new bins
is at most the number of unmatched points in this maximum matching. There are
two differences though. First, $\left|\overline{L_{j}}\right|$ may not be
greater than $\left|L_{j}\right|$; but as we have shown, w.h.p, the difference
can at most be $2\mathbb{E}\left[\mathcal{W}(I)\right]^{2/3}$. Secondly, in
the matching variant $\mathcal{M}$, every point has equal chance to be a plus
point or minus point. However, this is also inconsequential, since using
concentration bounds for binomial random variables, we can show that the
number of plus points/minus points lie in the range
$\left(\mathbb{E}\left[\left|\overline{L_{j}}\right|\right]\pm\mathbb{E}\left[\left|\overline{L_{j}}\right|\right]^{2/3}\right)$
w.h.p. Hence by Lemma 2.1, we obtain that there exist constants
$a_{3},C_{4},K_{1}$ s.t.

$\displaystyle\leq
C_{4}\exp\left(-a_{3}(\log\left|\overline{L_{j}}\right|)^{3/2}\right)$

We can simplify the above inequality using Equations 5 and 8 and the fact that
$\mathrm{Opt}(I)\leq 2\mathcal{W}(I)$ to obtain that there exist constants
$a_{4},C_{4},K_{2}>0$ such that, The only part left is to bound the number of
bins opened by small items in third way. Let this number be
$A_{\mathrm{small}}^{j}$. We will bound this by using the concentration of
weights of small items in $\overline{T_{j}}$ and $T_{j}$. Consider the random
variables $X_{1},X_{2}\ldots X_{n}$ where $X_{i}=0$ if $x_{i}$ is large, and
$X_{i}=x_{i}$ otherwise. We have that
$\mathcal{W}(S_{j})=\sum\limits_{X_{i}:x_{i}\in T_{j}}X_{i}$ and
$\mathcal{W}(\overline{S_{j}})=\sum\limits_{X_{i}:x_{i}\in\overline{T_{j}}}X_{i}$.
By applying Bernstein’s inequality (similar to Lemma 2.4) we get,
$\mathcal{W}(S_{j})\leq\frac{\left|T_{j}\right|}{n}\mathcal{W}(I_{s})+\mathbb{E}\left[\mathcal{W}(I)\right]^{2/3},\text{
and
}\mathcal{W}(\overline{S_{j}})\geq\frac{\left|\overline{T_{j}}\right|}{n}\mathcal{W}(I_{s})-\mathbb{E}\left[\mathcal{W}(I)\right]^{2/3}$
with a probability of at least
$1-C_{5}\exp\left(-a_{5}\mathbb{E}\left[\mathcal{W}(I)\right]^{1/3}\right)$
for some constants $C_{5},a_{5}>0$. Combining both, we get,

$\mathcal{W}(S_{j})\leq\mathcal{W}(\overline{S_{j}})+2\mathbb{E}\left[\mathcal{W}(I)\right]^{2/3}$
(10)

The initial allocated space for small items at the start of stage $j$ in the
packing $\mathcal{P}_{j}$ is $\mathcal{W}(\overline{S_{j}})$. Recall that
$B_{j}^{(k)}$ denotes the $k^{\mathrm{th}}$ bin in the packing of
$\mathcal{P}_{j}$. While packing the small items, if the $S$-slot in
$B_{j}^{(k)}$ cannot accommodate a small item, this means that the remaining
space in this $S$-slot is at most $\delta$. So, the weight of small items
which overflow the space allocated in packing $\mathcal{P}_{j}$ is at most
$\mathcal{W}(S_{j})-\mathcal{W}(\overline{S_{j}})+\delta\left|\mathcal{P}_{j}\right|$
and this entire weight is packed in new bins opened exclusively for small
items. Each of these bins (except possibly one) have an occupancy of at least
$(1-\delta)$. Since $\mathcal{A}_{\alpha}$ is $\alpha$-approximation
algorithm,
$\left|\mathcal{P}_{j}\right|=\mathcal{A}_{\alpha}(\overline{T_{j}})\leq\alpha\mathrm{Opt}(\overline{T_{j}})+o(\mathrm{Opt}(I))$.
Using Equations 7 and 10 we get,

$\displaystyle A_{\mathrm{small}}^{j}$
$\displaystyle\leq\frac{1}{1-\delta}\left(\mathcal{W}(S_{j})-\mathcal{W}(\overline{S_{j}})+\delta\cdot\alpha\mathrm{Opt}(\overline{T_{j}})+o(\mathrm{Opt}(I))\right)+1$
$\displaystyle\leq{2\delta}\cdot\alpha\frac{\left|\overline{T_{j}}\right|}{n}\mathbb{E}\left[\mathrm{Opt}(I)\right]+C_{3}\mathbb{E}\left[\mathrm{Opt}(I)\right]^{2/3}+o(\mathrm{Opt}(I))$
(11)

with high probability. Combining Equations 7, LABEL:open-unmatch and 11, the
number of bins, $A_{j}$, opened in the stage $j$ is bounded as,

$\displaystyle A_{j}$
$\displaystyle=A_{\mathrm{proxy}}^{j}+A_{\mathrm{unmatch}}^{j}+A_{\mathrm{small}}^{j}$
$\displaystyle\leq\alpha(1+{4\delta})\frac{\left|\overline{T_{j}}\right|}{n}\mathbb{E}\left[\mathrm{Opt}(I)\right]+C_{6}\mathbb{E}\left[\mathrm{Opt}(I)\right]^{2/3}+o(\mathrm{Opt}(I))$
$\displaystyle\leq\alpha(1+{4\delta})\frac{\left|T_{j}\right|}{n}\mathbb{E}\left[\mathrm{Opt}(I)\right]+C_{6}\mathbb{E}\left[\mathrm{Opt}(I)\right]^{2/3}+o(\mathrm{Opt}(I))$
(12)

w.h.p., for some constant $C_{6}$. To bound the sum of all $A_{j}$s, first
note that the number of “remaining stages” is ${m-1}$ which is a constant
dependent on $\delta$. Hence, with high probability,

$\displaystyle\sum\limits_{j=1}^{{m-1}}A_{j}$
$\displaystyle\leq\alpha(1+4\delta)\sum\limits_{j=1}^{{m-1}}\frac{\left|\overline{T_{j}}\right|}{n}\mathbb{E}\left[\mathrm{Opt}(I)\right]+{(m-1)}\cdot
C_{6}\mathbb{E}\left[\mathrm{Opt}(I)\right]^{2/3}+o(\mathrm{Opt}(I))$
$\displaystyle\leq\alpha(1+4\delta)\mathbb{E}\left[\mathrm{Opt}(I)\right]+C_{7}\mathbb{E}\left[\mathrm{Opt}(I)\right]^{2/3}+o(\mathrm{Opt}(I))$
(13)

for some constant $C_{7}>0$ dependent on $\delta$.

In the sampling phase, we have $\mathrm{NF}(T_{0})\leq
4\delta\mathbb{E}\left[\mathrm{Opt}(I)\right]$ with high probability and in
all the remaining phases we have
$\sum_{j=1}^{{m-1}}A_{j}\leq\alpha(1+4\delta)\mathbb{E}\left[\mathrm{Opt}(I)\right]+C_{7}\mathbb{E}\left[\mathrm{Opt}(I)\right]^{2/3}+o(\mathrm{Opt}(I))$.

Combining both the results we get that w.h.p. the number of bins opened by
$\mathtt{Alg}$ is,

$\displaystyle\mathtt{Alg}(I)$
$\displaystyle\leq\alpha(1+8\delta)\mathbb{E}\left[\mathrm{Opt}(I)\right]+C_{7}\mathbb{E}\left[\mathrm{Opt}(I)\right]^{2/3}+o(\mathrm{Opt}(I))$
$\displaystyle\leq\alpha(1+\varepsilon)\mathbb{E}\left[\mathrm{Opt}(I)\right]+C_{7}\mathbb{E}\left[\mathrm{Opt}(I)\right]^{2/3}+o(\mathrm{Opt}(I))$
(14)

In the low probability event when Equation 14 may not hold, we can bound
$\mathtt{Alg}(I)$ as follows. In the sampling stage, we have that
$\mathtt{Alg}(T_{0})\leq 2\mathrm{Opt}(I)-1$. For the remaining stages, we
bound the number of bins containing at least one large item and the number of
bins containing only small items. Because we create a proxy packing at the
start of each stage, each large item is packed at most $m$ times. So, the
number of bins containing at least one large item is at most
$m\left|I_{\ell}\right|$. In each stage, with one possible exception, every
bin opened which has only small items has an occupancy of at least
$(1-\delta)$. Combining over all the stages, the number of bins which contain
only small items is at most $\frac{1}{1-\delta}\mathcal{W}(I_{s})+m$. Thus, we
can bound the total number of bins used by $\mathtt{Alg}$ to be at most
$2\mathrm{Opt}(I)+m\left|I_{\ell}\right|+\frac{1}{1-\delta}\mathcal{W}(I_{s})+m$.
On the other hand, we know that
$\mathrm{Opt}(I)\geq\mathcal{W}(I)\geq\delta\left|I_{\ell}\right|+\mathcal{W}(I_{s})$.
Hence, we obtain that
$m\left|I_{\ell}\right|+\frac{1}{1-\delta}\mathcal{W}(I_{s})\leq\frac{m}{\delta(1-\delta)}\mathrm{Opt}(I)$.
Combining all these, we obtain that

$\displaystyle\mathtt{Alg}(I)\leq\left(2+\frac{m}{\delta(1-\delta)}\right)\mathrm{Opt}(I)+m$
(15)

Now, to obtain the competitive ratio, suppose Equation 14 holds with
probability $p(=1-o(1))$. We combine Equations 14 and 15 similar to the case
when $\left|L_{0}\right|\leq\delta^{3}\cdot\mathcal{W}(T_{0})$.

$\displaystyle\mathbb{E}\left[\mathtt{Alg}(I)\right]$ $\displaystyle\leq
p(\alpha(1+8\delta)\mathbb{E}\left[\mathrm{Opt}(I)\right]+o(\mathbb{E}\left[\mathrm{Opt}(I)\right]))$
$\displaystyle\qquad+(1-p)\left(\left(2+\frac{m}{\delta(1-\delta)}\right)\mathbb{E}\left[\mathrm{Opt}(I)\right]+m\right)$
$\displaystyle\leq\alpha(1+\varepsilon)\mathbb{E}\left[\mathrm{Opt}(I)\right]+o(\mathbb{E}\left[\mathrm{Opt}(I)\right])$
(since $1-p=o(1)$)

Scaling the initial value $\varepsilon$ to $\varepsilon/\alpha$ before the
start of the algorithm, we obtain a competitive ratio of $\alpha+\varepsilon$.

###  2.2 Getting Rid of the Assumption on the Knowledge of the Input Size

In this subsection, we will extend $\mathtt{Alg}$ for online bin packing with
i.i.d. items to devise an algorithm that guarantees essentially the same
competitive ratio without knowing the value of $n$. We denote this algorithm
by $\mathtt{ImpAlg}$.

We use a doubling trick as follows. We first guess the value of $n$ to be a
constant $n_{0}:=1/\delta^{3}$. Then, we run $\mathtt{Alg}$ until
$\min\\{n,n_{0}\\}$ items arrive (here, if $\min\\{n,n_{0}\\}=n$, then it
means that the input stream has ended). If $n>n_{0}$, i.e., if there are more
items to arrive, then we revise our estimate of $n$ by doubling it, i.e., the
new value of $n$ is set as $n_{1}:=2n_{0}$. We start $\mathtt{Alg}$ afresh on
the next $\min\\{n,n_{1}\\}-n_{0}$ items. If $n>2n_{0}$, then we set the new
guess of $n$ to be $n_{2}:=2n_{1}=2^{2}n_{0}$ and start $\mathtt{Alg}$ afresh
on the next $\min\\{n,n_{2}\\}-n_{1}$ number of items. We continue this
process of doubling our estimate of $n$ until all the items arrive. See Figure
1 for an illustration. The pseudocode is provided in Algorithm 2 in the
Appendix.

Figure 1: Doubling trick visualized. We start off with an estimate of $n$ to
be $n_{0}$ and keep doubling it. The first and second super-stages contain
$n_{0}$ items each. The third super-stage contains $2n_{0}$ items and so on.
Each super-stage is packed individually using $\mathtt{Alg}$. The stages in
each super-stage are marked by $\bullet$ (for simplicity, only the stages in
the last two super-stages are marked). The $\boldsymbol{\times}$ mark
indicates the point where the input abruptly stopped. Notice how the fifth
stage of the last super-stage is not full. Just before packing this stage,
$\mathtt{Alg}$ constructs a proxy packing of $\chi$ by using
$\mathcal{A}_{\alpha}$. But this is very lossy since $\chi$ is large compared
to this last stage.

We consider the following partition of the entire input into super-stages as
follows: The first super-stage, $\Gamma_{0}$, contains the first $n_{0}$
items. The second super-stage, $\Gamma_{1}$, contains the next $n_{1}-n_{0}$
items. In general, for $i>0$, the $(i+1)^{\mathrm{th}}$ super-stage,
$\Gamma_{i}$, contains $\min\\{n_{i},n\\}-n_{i-1}$ items which are given by
$x_{n_{i-1}+1},x_{n_{i-1}+2},\dots,x_{\min\\{n,n_{i}\\}}$. So, essentially,
$\mathtt{ImpAlg}$ can be thought of running $\mathtt{Alg}$ on each super-stage
separately. The number of super-stages is given by
$\kappa:=\left\lceil\log(n/n_{0})\right\rceil$. The last super-stage might not
be _full_ , i.e., ideally, it should contain $n/2$ items but it may not. An
even worse case would be when the last stage of the last super-stage is not
full, i.e., when it contains fewer than $\left|\Gamma_{\tau-1}\right|/2$ items
where $\Gamma_{\tau-1}$ is the last super-stage. To see why this is bad, note
that since we had assumed the value of $n$ in $\mathtt{Alg}$, it was possible
to make sure that the last stage had exactly $n/2$ items. This is crucial
because our analysis heavily relied on the fact that
$\left|T_{j}\right|=\left|\overline{T_{j}}\right|$ for any stage $T_{j}$. This
meant that the item set $T_{j}$ fit almost perfectly in the proxy packing of
$\overline{T_{j}}$. But if the last stage $T_{m-1}$ contains far fewer items
than $\overline{T_{m-1}}$, then we might be opening far too many proxy bins
than required (see the description of the last super-stage in Figure 1).
Hence, we need a slight tweak in $\mathtt{Alg}$ in the way it packs a stage.

####  2.2.1 A Tweak to $\mathtt{Alg}$ in the Way in which a Stage is Packed

Recall that for any $j>1$, we pack $T_{j}$ as follows. Just before the stage
$T_{j}$ starts, we pack $\overline{T_{j}}$ using $\mathcal{A}_{\alpha}$ (the
proxy packing). Instead of packing the entire set $\overline{T_{j}}$ at once,
we do this in chunks. We divide the entire set $\overline{T_{j}}$ into
$\eta:=1/\delta$ number of _equal_ chunks. Let’s denote these chunks by
$\overline{T_{j}}^{(1)},\overline{T_{j}}^{(2)},\dots,\overline{T_{j}}^{(\eta)}$.
Suppose each chunk contains $c_{j}$ number of items. We first pack
$\overline{T_{j}}^{(1)}$ using $\mathcal{A}_{\alpha}$ . Let this packing be
denoted by $\mathcal{P}_{j}^{(1)}$. We pack the first $c_{j}$ items of $T_{j}$
by fitting them in the packing $\mathcal{P}_{j}^{(1)}$ just like we packed a
stage in $\mathtt{Alg}$ by creating $S$-slots for small items and replacing a
proxy item if we need to pack a large item. Then, we pack
$\overline{T_{j}}^{(2)}$ using $\mathcal{A}_{\alpha}$ and fit the next $c_{j}$
items of $T_{j}$ in this packing just like before. We continue this process
until all the items in $T_{j}$ are packed. This way, if the size of $T_{j}$ is
very small compared to that of $\overline{T_{j}}$, then we only compute the
proxy packing of only a few chunks and not of the entire set
$\overline{T_{j}}$. On the other hand, if $\left|T_{j}\right|$ is significant
when compared to $\left|\overline{T_{j}}\right|$, then we are anyway good
since the number of chunks $\eta$ is a constant. Intuitively, the optimal
solution for $\overline{T_{j}}$ and the union of optimal solutions for $\eta$
chunks
$\overline{T_{j}}^{(1)},\overline{T_{j}}^{(2)},\dots,\overline{T_{j}}^{(\eta)}$
are close enough when $\eta$ is a constant. See $\mathtt{PackStage}$
(Algorithm 3 in the Appendix) for details.

####  2.2.2 Analysis

The analyses of both $\mathtt{ImpAlg}$ and the tweak to $\mathtt{Alg}$ can be
found in Section A.5. The intuition to why the tweak to $\mathtt{Alg}$ doesn’t
cause much problem has already been provided above. The analysis of
$\mathtt{ImpAlg}$ is a bit complicated though. When $n$ was known we had
$O(1)$ stages. However, now we can have
$\kappa=\left\lceil\log(n/n_{0})\right\rceil$ number of super-stages. There
can arise two problems:

  * •

We can not analyze each super-stage individually and then sum up the
performance guarantees, as we can not use union bound for a super-constant
number of events. Moreover, we can’t even use the analysis of $\mathtt{Alg}$
for the first few super-stages since they might only have a constant number of
items. So, we consider the
$\kappa_{1}:=\left\lceil\log(\delta^{7}n)\right\rceil$ number of the initial
super-stages at a time. We show that these initial super-stages contain only a
small fraction of the entire input. Each of the final $(\kappa-\kappa_{1})$
super-stages can be individually analyzed using the analysis of
$\mathtt{Alg}$.

  * •

For each super-stage, we can have a constant number of $S$-bins (bins which
contain only small items) with less occupancy. However, since the number of
super-stages itself is a super-constant, this can result in a lot of wasted
space. For this, we exploit the monotonicity of NF to ensure that we can pack
small items from a super-stage into empty slots for small items from the
previous stages.

See Section A.5.2 for the details.

##  3 Best-Fit under the Random-Order Model

In this section, we will prove Theorems 1.4 and 1.3.

###  3.1 When Item Sizes are Larger than $1/3$

First, let us recall upright matching and a related result that we will be
using.

Upright Matching Problem.  For a positive integer $k$, let $S_{k}$ denote the
set of all permutations of $[k]$. Consider a set of points $P$ in the two-
dimensional coordinate system. Suppose each item is marked as a _plus_ point
or a _minus_ point. Let $P^{+}$ denote the set of plus points and let $P^{-}$
denote the set of minus points. An edge exists between two points
$p^{+},p^{-}$ iff $p^{+}\in P^{+},p^{-}\in P^{-}$ and iff $p^{+}$ lies above
and to the right of $p^{-}$, i.e., both the coordinates of $p^{+}$ are greater
than or equal to the corresponding coordinates of $p^{-}$. The objective is to
find a maximum matching in this graph or, in other words, minimize the number
of unmatched points. We denote the number of unmatched points by $U(P)$.

We will use the following variant of upright matching to prove the final
result. Refer to [9] for the proof of the following lemma.

######  Lemma 3.1.

[9] Let $k\in\mathbb{N}$ and let $\mathcal{A}=\\{a_{1},a_{2},\dots,a_{2k}\\}$
such that $a_{i}\geq a_{k+i}$ for all $i\in[k]$. Define a set of _plus_ points
$P^{+}=\\{(i,a_{i}):i\in[k]\\}$ and a set of _minus_ points
$P^{-}=\\{(i,a_{i}):k<i\leq 2k\\}$. Suppose we randomly permute the
$x$-coordinates of $P^{+}\cup P^{-}$, i.e., for a uniform random permutation
$\pi\in S_{2k}$, we redefine $P^{+}$ and $P^{-}$ as
$P^{+}=\\{(\pi(i),a_{i}):i\in[k]\\}$ and $P^{-}=\\{(\pi(i),a_{i}):k<i\leq
2k\\}$. Let $P=P^{+}\cup P^{-}$. Then, there exist universal constants
$a,C,K>0$ such that

######  Remark 3.2.

In the above lemma, if we change the definitions of $P^{+},P^{-}$ to be
$P^{+}_{\mathrm{new}}=\\{(-\pi(i),a_{i}):i\in[k]\\}$,
$P^{-}_{\mathrm{new}}=\\{(-\pi(i),a_{i}):k<i\leq 2k\\}$, the guarantee given
by LABEL:upright-bf13 doesn’t change since the new set
$P^{+}_{\mathrm{new}}\cup P^{-}_{\mathrm{new}}$ can be constructed by taking a
mirror image of the original set $P^{+}\cup P^{-}$ with respect to the
$y$-axis. Since we consider random permutations, the probability of a set and
its mirror image is the same.

With the above lemma and remark at hand, we now proceed to prove Theorem 1.3.
Albers et al. [1] showed that the asymptotic random order ratio of the Best-
Fit algorithm is at most $1.25$ when all the item sizes are more than $1/3$.
In this section, we improve it further and show that, Best-Fit for this
special case under the random-order model is nearly optimal. We first show
that the Modified Best-Fit algorithm [11] is nearly optimal and we analyze
this using the above variant of stochastic upright matching. The Modified
Best-Fit (MBF) algorithm is the same as BF except that it closes a bin if it
receives an item of size less than $1/2$. Shor[44] showed that MBF _dominates_
BF, i.e., for any instance $I$, $\mathrm{BF}(I)\leq\mathrm{MBF}(I)$. MBF can
be easily reduced to upright matching as follows. Given an instance
$I=\\{x_{1},\ldots,x_{n}\\}$, for any item $x_{i}\in I$, $x_{i}\in P^{-}$ if
$x_{i}\leq 1/2$ with $x$-coordinate as $-i$ and $y$-coordinate as $x_{i}$, and
$x_{i}\in P^{+}$ if $x_{i}>1/2$ with $x$-coordinate as $-i$ and $y$-coordinate
as $1-x_{i}$. So, any item $x_{s}$ of size $\leq 1/2$ can be matched with an
item $x_{\ell}$ of size $>1/2$ if and only if, $x_{\ell}$ arrives before
$x_{s}$ and the remaining space in the bin occupied by $x_{\ell}$ is more than
the size of $x_{s}$.

Define an item $x_{i}$ as a large item ($L$) if $x_{i}>1/2$; otherwise, as a
medium item ($M$) if $x_{i}\in(1/3,1/2]$. We define a bin as $LM$-bin if it
contains one large item and one medium item. We use the following lemma which
was proved in [1] using the monotonicity property of BF when all item sizes
are more than $1/3$.

######  Lemma 3.3.

[1] Let $I$ be any list that can be packed into $\mathrm{Opt}(I)$ number of
$LM$-bins. If Best-Fit has an AAR of $\alpha$ for $I$, then it has an AAR of
$\alpha$ for any list of items larger than $1/3$ as well.

Consider an input instance which has an optimal packing containing only
$LM$-bins. Consider the number of bins opened by MBF for such instances. Each
large item definitely opens a new bin, and a medium item opens a new bin if
and only if it can not be placed along with a large item, i.e., it is
“unmatched”. So, the number of bins opened by MBF equals (number of large
items$+$number of unmatched medium items). Now, we will prove our result.

######  Theorem 3.4.

For any list $I$ of items larger than $1/3$, the asymptotic random order ratio
$RR_{BF}^{\infty}=1$.

######  Proof 3.5.

From Lemma 3.3, it is enough to prove the theorem for any list $I$ that can be
packed in $\mathrm{Opt}(I)$ $LM$-bins. So, we can assume that $I$ has $k$
large items and $k$ medium items where $\mathrm{Opt}(I)=k$. Now consider the
packing of $\mathrm{MBF}$ for a randomly permuted list $I_{\sigma}$. We have,
$\mathrm{MBF}(I_{\sigma})=(k+\text{number of unmatched {medium} items}).$
Since the optimal packing has all the items matched, we can reduce the
following case into the matching variant in Lemma 3.1: Let $\ell_{i},m_{i}$
denote the sizes of the large item and the medium item respectively in the
$i^{\mathrm{th}}$ bin of the optimal solution. For $i\in[k]$, we let
$a_{i}=1-\ell_{i}$ and $a_{k+i}=m_{i}$ and let
$\mathcal{A}=\\{a_{1},a_{2},\dots,a_{2k}\\}$. Note that the required condition
in Lemma 3.1, i.e., $a_{i}\geq a_{k+i}$ is satisfied. The arrival order is
randomly sampled from $S_{2k}$. So, we have

$\mathrm{MBF}(I_{\sigma})=k+{\frac{U(P)}{2}}\leq k+K\sqrt{k}(\log k)^{3/4}$

with probability of at least $1-C\exp(-a(\log k)^{3/2})$ for some universal
constants $a,C,K>0$. Since $\mathrm{MBF}$ dominates $\mathrm{BF}$ we have

In case the high probability event does not occur, we can use the bound of
$\mathrm{BF}(I)\leq 1.7\mathrm{Opt}(I)+2$. Let $p:=C\exp(-a(\log k)^{3/2})$.
Then

$\displaystyle\mathbb{E}\left[\mathrm{BF}(I_{\sigma})\right]$
$\displaystyle\leq
p(1.7\mathbb{E}\left[k\right]+2)+(1-p)(\mathbb{E}\left[k\right]+K\sqrt{\mathbb{E}\left[k\right]}(\log\mathbb{E}\left[k\right])^{3/4})$
$\displaystyle\leq\mathbb{E}\left[\mathrm{Opt}(I)\right]+o(\mathbb{E}\left[\mathrm{Opt}(I)\right])$
(since $p=o(1)$)

So, we get:
$RR_{BF}^{\infty}=\limsup\limits_{k\rightarrow\infty}\left(\sup\limits_{I:\mathrm{Opt}(I)=k}(\mathbb{E}[\mathrm{BF}(I_{\sigma})]/\mathrm{Opt}(I))\right)=1.$
This completes the proof.

###  3.2 The $3$-Partition Problem under Random-Order Model

In this section, we analyze the Best-Fit algorithm under the random-order
model given that the item sizes lie in the range $(1/4,1/2]$, and thus prove
Theorem 1.4. We call an item _small_ if its size lies in the range $(1/4,1/3]$
and _medium_ if its size lies in the range $(1/3,1/2]$. Let $I$ be the input
list of items and let $n:=\left|I\right|$. Recall that given $\sigma$, a
uniform random permutation of $[n]$, $I_{\sigma}$ denotes the list $I$
permuted according to $\sigma$. We denote by $\mathrm{Opt}(I_{\sigma})$, the
number of bins used in the optimal packing of $I_{\sigma}$ and by
$\mathrm{BF}(I_{\sigma})$, the number of bins used by Best-Fit to pack
$I_{\sigma}$. Note that $\mathrm{Opt}(I_{\sigma})=\mathrm{Opt}(I)$.

If there exists a set of three small items in $I_{\sigma}$ such that they
arrive as three consecutive items, we call that set to be an _$S$ -triplet_.
We call a bin to be a $k$-bin if it contains exactly $k$ items, for
$k\in\\{1,2,3\\}$. We sometimes refer to a bin by mentioning its contents more
specifically as follows: An $MS$-bin is a $2$-bin which contains a medium item
and a small item. Similarly, an $SSS$-bin is a $3$-bin which contains three
small items. Likewise, we can define an $M$-bin, $S$-bin, $MM$-bin, $SS$-bin,
$MMS$-bin, and $MSS$-bin.

Since the item sizes lie in $(1/4,1/2]$, any bin in the optimal packing
contains at most three items. For the same reason, in the packing by Best-Fit,
every bin (with one possible exception) contains at least two items. This
trivially shows that the ECR of Best-Fit is at most $3/2$. To break the
barrier of $3/2$, we use the following observations.

  * •

Any $3$-bin must contain a small item.

  * •

So, if the optimal solution contains a lot of $3$-bins, then it means that the
input set contains a lot of small items.

We will prove that if there exist many small items in the input, then with
high probability, in a random permutation of the input, there exist many
disjoint $S$-triplets.

######  Claim 18.

Let $m$ be the number of small items in the input set $I$, and let
$X_{\sigma}$ denote the maximum number of mutually disjoint $S$-triplets in
$I_{\sigma}$. Suppose $m\geq cn$ where $c=0.00033$, then the following
statements hold true:

  1. 1.

$\mathbb{E}\left[X_{\sigma}\right]\geq m^{3}/(3n^{2}){\geq c^{3}n/3}$.

  2. 2.

$X_{\sigma}\geq{c^{3}n/3-o(n)}$ with high probability.

Then, we prove that Best-Fit packs at least one small item from an $S$-triplet
in a $3$-bin or in an $SS$-bin.

######  Claim 19.

Let $\\{S_{1},S_{2},S_{3}\\}$ be an $S$-triplet in $I$ such that $S_{3}$
follows $S_{2}$ which in turn follows $S_{1}$. Then, in the final packing of
Best-Fit of $I$, at least one of $S_{1},S_{2},S_{3}$ is packed in a $3$-bin or
in an $SS$-bin.∎

But the number of $SS$-bins in the final packing of Best-Fit can be at most
one. So, we obtain that the number of $3$-bins in the Best-Fit packing is
significant. With these arguments, the proof of Theorem 1.4 follows. The
detailed proofs of the above two claims and the final theorem is given in
Appendix B.

##  4 Conclusion

We studied online bin packing under two stochastic settings, namely the i.i.d.
model, and the random-order model. For the first setting, we devised a meta-
algorithm which takes any offline algorithm $\mathcal{A}_{\alpha}$ with an AAR
of $\alpha$ (where $\alpha$ can be any constant $\geq 1$), and produces an
online algorithm with an ECR of $(\alpha+\varepsilon)$. This shows that online
bin packing under the i.i.d. model and offline bin packing are almost
equivalent. Using any AFPTAS as $\mathcal{A}_{\alpha}$ results in an online
algorithm with an ECR of $(1+\varepsilon)$ for any constant $\varepsilon>0$.
An interesting question of theoretical importance is to find whether achieving
an ECR of $1$ is possible or not. Another related open question is if we can
settle online bin packing under the random-order model as well.

Then, we studied the analysis of the well-known Best-Fit algorithm under the
random-order model. First, we proved that the ECR of Best-Fit is equal to one
if all the item sizes are greater than $1/3$. Then, we improved the analysis
of the Best-Fit from $1.5$ to $\approx 1.4941$, for the special case when the
item sizes are in the range $(1/4,1/2]$. An open question is to further
improve this analysis since these instances are conjectured to be the hardest
(offline) instances of bin packing. Another interesting problem would be to
improve the lower bound on the ECR of Best-Fit in this model (which is
currently $1.1$ due to [2]).

## References

  * [1] Susanne Albers, Arindam Khan, and Leon Ladewig.  Best fit bin packing with random order revisited.  Algorithmica, 83(9):2833–2858, 2021.
  * [2] 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.
  * [3] Brenda S Baker and Edward G Coffman, Jr.  A tight asymptotic bound for next-fit-decreasing bin-packing.  SIAM Journal on Algebraic Discrete Methods, 2(2):147–152, 1981\.
  * [4] 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 ESA, volume 112, pages 5:1–5:14, 2018.
  * [5] 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.
  * [6] Nikhil Bansal, Marek Eliás, and Arindam Khan.  Improved approximation for vector bin packing.  In SODA, pages 1561–1579, 2016.
  * [7] Jozsef Bekesi, Gabor Galambos, and Hans Kellerer.  A 5/4 linear time bin packing algorithm.  Journal of Computer and System Sciences, 60(1):145–160, 2000.
  * [8] Jon Louis Bentley, David S Johnson, Frank Thomson Leighton, Catherine C McGeoch, and Lyle A McGeoch.  Some unexpected expected behavior results for bin packing.  In STOC, pages 279–288, 1984.
  * [9] 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\.
  * [10] 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.
  * [11] 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.
  * [12] 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.
  * [13] Edward G Coffman Jr, Kimming So, Micha Hofri, and AC Yao.  A stochastic model of bin-packing.  Information and Control, 44(2):105–115, 1980.
  * [14] Janos Csirik, David S Johnson, Claire Kenyon, James B Orlin, Peter W Shor, and Richard R Weber.  On the sum-of-squares algorithm for bin packing.  Journal of the ACM (JACM), 53(1):1–65, 2006.
  * [15] 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.
  * [16] Brian C Dean, Michel X Goemans, and Jan Vondrák.  Approximating the stochastic knapsack problem: The benefit of adaptivity.  Mathematics of Operations Research, 33(4):945–964, 2008.
  * [17] Friedrich Eisenbrand, Dömötör Pálvölgyi, and Thomas Rothvoß.  Bin packing via discrepancy of permutations.  In SODA, pages 476–481, 2011.
  * [18] Jon Feldman, Aranyak Mehta, Vahab Mirrokni, and Shan Muthukrishnan.  Online stochastic matching: Beating 1-1/e.  In FOCS, pages 117–126, 2009.
  * [19] Thomas S Ferguson.  Who solved the secretary problem?  Statistical science, 4(3):282–289, 1989.
  * [20] Carsten Fischer and Heiko Röglin.  Probabilistic analysis of the dual next-fit algorithm for bin covering.  In LATIN, pages 469–482, 2016.
  * [21] Carsten Fischer and Heiko Röglin.  Probabilistic analysis of online (class-constrained) bin packing and bin covering.  In LATIN, volume 10807, pages 461–474. Springer, 2018.
  * [22] Anupam Gupta, Ravishankar Krishnaswamy, and R Ravi.  Online and stochastic survivable network design.  SIAM Journal on Computing, 41(6):1649–1672, 2012.
  * [23] Anupam Gupta, Amit Kumar, Viswanath Nagarajan, and Xiangkun Shen.  Stochastic load balancing on unrelated machines.  Mathematics of Operations Research, 46(1):115–133, 2021.
  * [24] Anupam Gupta and Sahil Singla.  Random-order models.  In Beyond the Worst-Case Analysis of Algorithms, pages 234–258. Cambridge University Press, 2020.
  * [25] Rebecca Hoberg and Thomas Rothvoss.  A logarithmic additive integrality gap for bin packing.  In SODA, pages 2616–2625, 2017.
  * [26] David S Johnson.  Near-optimal bin packing algorithms.  PhD thesis, Massachusetts Institute of Technology, 1973.
  * [27] David S Johnson.  Fast algorithms for bin packing.  J. Comput. Syst. Sci., 8(3):272–314, 1974.
  * [28] 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.
  * [29] David S Johnson and Michael R Garey.  A 71/60 theorem for bin packing.  J. Complex., 1(1):65–106, 1985.
  * [30] Edward G Coffman Jr, János Csirik, Lajos Rónyai, and Ambrus Zsbán.  Random-order bin packing.  Discret. Appl. Math., 156(14):2810–2816, 2008.
  * [31] Narendra Karmarkar and Richard M Karp.  An efficient approximation scheme for the one-dimensional bin-packing problem.  In FOCS, pages 312–320, 1982.
  * [32] Claire Kenyon.  Best-fit bin-packing with random order.  In SODA, pages 359–364, 1996.
  * [33] Chan C Lee and Der-Tsai Lee.  A simple on-line bin-packing algorithm.  J. ACM, 32(3):562–572, July 1985.
  * [34] Chan C Lee and Der-Tsai Lee.  Robust on-line bin packing algorithms.  Technical Report, Northwestern University, 1987.
  * [35] Tom Leighton and Peter Shor.  Tight bounds for minimax grid matching with applications to the average case analysis of algorithms.  Combinatorica, 9(2):161–187, 1989.
  * [36] 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.
  * [37] Frank D Murgolo.  Anomalous behavior in bin packing algorithms.  Discret. Appl. Math., 21(3):229–243, 1988.
  * [38] Alantha Newman, Ofer Neiman, and Aleksandar Nikolov.  Beck’s three permutations conjecture: A counterexample and some consequences.  In FOCS, pages 253–262, 2012.
  * [39] Prakash V Ramanan.  Average-case analysis of the smart next fit algorithm.  Inf. Process. Lett., 31(5):221–225, 1989.
  * [40] W. T. Rhee.  Inequalities for bin packing-iii.  Optimization, 29(4):381–385, 1994.  arXiv:https://doi.org/10.1080/02331939408843965, doi:10.1080/02331939408843965.
  * [41] Wansoo T Rhee and Michel Talagrand.  Exact bounds for the stochastic upward matching problem.  Transactions of the American Mathematical Society, 307(1):109–125, 1988.
  * [42] 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.
  * [43] Wansoo T Rhee and Michel Talagrand.  On line bin packing with items of random size.  Mathematics of Operations Research, 18(2):438–445, 1993.
  * [44] Peter W Shor.  The average-case analysis of some on-line algorithms for bin packing.  Combinatorica, 6(2):179–200, 1986.
  * [45] Joel Spencer.  Ten lectures on the probabilistic method.  SIAM, 1994.

##  Appendix A Omitted Details from Section 2

###  A.1 Omitted Proof of Lemma 2.3

The following claim follows directly from Theorem 2.1 in [42].

######  Claim 20.

Let $I$ be a list of $n$ items sampled independently from a distribution and
let $I(1,t)$ denote the first $t$ items. Then there exist constants
$K_{1},a_{1}>0$ such that

The next claim is a direct implication of the main result of [40].

######  Claim 22.

Let $I$ be a list of $n$ items sampled independently from a distribution. Then
there exist constants $K_{2},a_{2}>0$ such that

Combining both the claims, we obtain that there exist constants $K,a>0$ such
that

###  A.2 Omitted Proof of Lemma 2.4

We can assume that $\mathcal{W}(I)$ goes to infinity since we know that
$\mathrm{Opt}(I)\leq 2\mathcal{W}(I)+1$. Let
$K:=\mathbb{E}\left[\mathcal{W}(I)\right]$ and $\mathcal{W}(x)$ be the weight
of item $x$. Using Bernstein’s inequality (Lemma 2.2),

$\displaystyle\leq\>$ $\displaystyle
2\exp\left(-\frac{K^{4/3}}{2\left(\sum_{x\in
J}\mathbb{E}\left[\mathcal{W}(x)\right]+K^{2/3}/3\right)}\right)$
$\displaystyle\leq\>$ $\displaystyle
2\exp\left(-\frac{K^{4/3}}{2\left(K+K^{2/3}/3\right)}\right)$
$\displaystyle\leq\>$ $\displaystyle
2\exp\left(-\frac{K^{4/3}}{2\left(K+K/3\right)}\right)$ (since $K$ goes to
infinity, $K^{2/3}\leq K$) $\displaystyle\leq\>$ $\displaystyle
2\exp\left(-\frac{1}{3}K^{1/3}\right).$

Since $\sum_{x\in J}\mathcal{W}(x)=\mathcal{W}(J)$ and since
$\mathbb{E}\left[\mathcal{W}(J)\right]=\frac{\left|J\right|}{n}\mathbb{E}\left[\mathcal{W}(I)\right]$,
the lemma follows.

###  A.3 Omitted Proof of Lemma 2.5

We can assume that $\mathcal{W}(I)$ goes to infinity. Let
$K:=\mathbb{E}\left[\mathcal{W}(I)\right]$. For any item $x$, let $L_{x}$ be
the indicator random variable which denotes if the item $x$ is a large item or
not. Using Bernstein’s inequality (Lemma 2.2),

$\displaystyle\leq\>$ $\displaystyle
2\exp\left(-\frac{K^{4/3}}{2\left(\sum_{x\in
J}\mathbb{E}\left[L_{x}\right]+K^{2/3}/3\right)}\right)$ $\displaystyle=\>$
$\displaystyle
2\exp\left(-\frac{K^{4/3}}{2\left(\mathbb{E}\left[\left|J_{\ell}\right|\right]+K^{2/3}/3\right)}\right)$
(since $\sum_{x\in J}L_{x}=\left|J_{\ell}\right|$) $\displaystyle\leq\>$
$\displaystyle
2\exp\left(-\frac{K^{4/3}}{2\left(K/\delta+K^{2/3}/3\right)}\right)$ (since
$K=\mathbb{E}\left[\mathcal{W}(I)\right]\geq\delta\mathbb{E}\left[\left|J_{\ell}\right|\right]$)
$\displaystyle\leq\>$ $\displaystyle
2\exp\left(-\frac{\delta}{3}K^{1/3}\right).$

Since $\sum_{x\in J}L_{x}=\left|J_{\ell}\right|$ and since
$\mathbb{E}\left[\left|J_{\ell}\right|\right]=\frac{\left|J\right|}{n}\mathbb{E}\left[\left|I_{\ell}\right|\right]$,
the lemma follows.

###  A.4 Omitted Proof of Lemma 2.6

Let’s denote the set of large items in $I(1,t)$ by $I_{\ell}(1,t)$ and denote
the set of small items by $I_{s}(1,t)$. Consider any optimal packing of
$I_{\ell}(1,t)$. Start packing $I_{s}(1,t)$ in the spaces left in the bins
greedily using Next-Fit while opening new bins whenever necessary. This gives
us a valid packing of $I(1,t)$.

If we don’t open any new bins to pack $I_{s}(1,t)$, then by Lemma 2.3 for some
constants $C_{1},C_{2}>0$,

$\displaystyle\mathrm{Opt}(I(1,t))$
$\displaystyle\leq\mathrm{Opt}\left(I_{\ell}(1,t)\right)$
$\displaystyle\leq\frac{\left|I_{\ell}(1,t)\right|}{\left|I_{\ell}\right|}\mathbb{E}\left[\mathrm{Opt}(I_{\ell})\right]+C_{1}\sqrt{\mathbb{E}\left[\left|I_{\ell}\right|\right]}(\log\mathbb{E}\left[\left|I_{\ell}\right|\right])^{3/4}$
(using Lemma 2.3)
$\displaystyle\leq\frac{\left|I_{\ell}(1,t)\right|}{\left|I_{\ell}\right|}\mathbb{E}\left[\mathrm{Opt}(I_{\ell})\right]+\mathbb{E}\left[\left|I_{\ell}\right|\right]^{2/3}$
$\displaystyle\leq\frac{\frac{t}{n}\left|\mathbb{E}\left[\left|I_{\ell}\right|\right]\right|+\mathbb{E}\left[\mathcal{W}(I)\right]^{2/3}}{\left|I_{\ell}\right|}\mathbb{E}\left[\mathrm{Opt}(I_{\ell})\right]+\mathbb{E}\left[\left|I_{\ell}\right|\right]^{2/3}$
(using Lemma 2.5)
$\displaystyle\leq\frac{\frac{t}{n}\left(\left|I_{\ell}\right|+\mathbb{E}\left[\mathcal{W}(I)\right]^{2/3}\right)+\mathbb{E}\left[\mathcal{W}(I)\right]^{2/3}}{\left|I_{\ell}\right|}\mathbb{E}\left[\mathrm{Opt}(I_{\ell})\right]+\mathbb{E}\left[\left|I_{\ell}\right|\right]^{2/3}$
(using Lemma 2.5)
$\displaystyle\leq\frac{t}{n}\mathbb{E}\left[\mathrm{Opt}(I)\right]+C_{1}\mathbb{E}\left[\mathrm{Opt}(I)\right]^{2/3}$
(using $\mathcal{W}(I)\geq\delta\left|I_{\ell}\right|$)

with probability at least
$1-\exp\left(-a(\log\mathbb{E}\left[\mathrm{Opt}(I)\right])^{1/3}\right)$ for
some constants $a,C_{1}>0$.

On the other hand, if we open new bins while packing $I_{s}(1,t)$, then after
the final packing, every bin (except possibly one) is filled to a level of at
least $1-\delta$. Hence, in this case,

$\displaystyle\mathrm{Opt}(I(1,t))$
$\displaystyle\leq\frac{1}{1-\delta}\mathcal{W}(I(1,t))+1$
$\displaystyle\leq(1+2\delta)\frac{t}{n}\mathbb{E}\left[\mathcal{W}(I)\right]+(1+2\delta)\mathbb{E}\left[\mathcal{W}(I)\right]^{2/3}+1$
$\displaystyle\leq(1+2\delta)\frac{t}{n}\mathbb{E}\left[\mathrm{Opt}(I)\right]+C_{2}\mathbb{E}\left[\mathrm{Opt}(I)\right]^{2/3}$
(using $\mathrm{Opt}(I)\geq\mathcal{W}(I)$ and $(1-\delta)(1+2\delta)\geq 1$
for $\delta<1/2$)

with probability at least
$1-\exp\left(-b\mathbb{E}\left[\mathrm{Opt}(I)\right]^{1/3}\right)$ for some
constants $b,C_{2}>0$. This completes the proof.

###  A.5 Details of Section 2.2

Algorithm 2 $\mathtt{ImpAlg}$: Improving $\mathtt{Alg}$ to get rid of the
assumption on the knowledge of the number of items

1:Input: $I_{n}(\mathcal{D})=\\{x_{1},x_{2},...,x_{n}\\}$.

2:$n_{-1}\leftarrow 0;n_{0}\leftarrow\frac{1}{\delta^{3}};\mathrm{for\>}j\geq
1,n_{j}=2n_{j-1}$

3:$i\leftarrow 0$

4:while true do

5: Run $\mathtt{Alg}(x_{n_{i-1}+1},x_{n_{i-1}+2},\dots,x_{\min\\{n_{i},n\\}})$

6: if the input stream has ended then

7: return the packing

8: else

9: $i\leftarrow i+1$

10: end if

11:end while

####  A.5.1 Analysis of the Tweak in $\mathtt{Alg}$ to Pack a Stage

We will now analyze the number of bins used for a stage with the change of
creating the proxy packing in chunks. Let $\eta^{\prime}$ be the final value
of $k$ in $\mathtt{PackStage}$ when it is run on $T_{j}$. The value of
$\eta^{\prime}$ indicates the number of chunks of $\overline{T_{j}}$ for which
we have computed the packing by $\mathcal{A}_{\alpha}$. For
$p\in[\eta^{\prime}]$, let $T_{j}^{(p)}$ denote the set of items in $T_{j}$
that we packed when $k=p$ in the run of $\mathtt{PackStage}$, i.e., in the
iteration when we consider the chunk $\overline{T_{j}}^{(p)}$. Note that for
all $p\in[\eta^{\prime}-1]$, we have that
$\left|T_{j}^{(p)}\right|=\left|\overline{T_{j}}^{(p)}\right|$. Let
$A_{j}^{(p)}$ denote the number of bins used to pack $T_{j}^{(p)}$. Hence,
from the analysis of $\mathtt{Alg}$, specifically Equation 12, we obtain that
with high probability, for some constant $C$,

$\displaystyle A_{j}^{(p)}$
$\displaystyle\leq\alpha(1+{4\delta})\frac{\left|\overline{T_{j}}^{(p)}\right|}{n}\mathbb{E}\left[\mathrm{Opt}(I)\right]+C\mathbb{E}\left[\mathrm{Opt}(I)\right]^{2/3}+o(\mathrm{Opt}(I))$
$\displaystyle=\alpha(1+{4\delta})\frac{\left|T_{j}^{(p)}\right|}{n}\mathbb{E}\left[\mathrm{Opt}(I)\right]+C\mathbb{E}\left[\mathrm{Opt}(I)\right]^{2/3}+o(\mathrm{Opt}(I))$
(17)

For $p=\eta^{\prime}$, it might be the case that
$\left|T_{j}^{(p)}\right|<\left|\overline{T_{j}}^{(p)}\right|$. So, the
following inequalities can be derived, which hold with high probability.

$\displaystyle A_{j}^{(\eta^{\prime})}$
$\displaystyle\leq\alpha(1+{4\delta})\frac{\left|\overline{T_{j}}^{(\eta^{\prime})}\right|}{n}\mathbb{E}\left[\mathrm{Opt}(I)\right]+C\mathbb{E}\left[\mathrm{Opt}(I)\right]^{2/3}+o(\mathrm{Opt}(I))$
$\displaystyle\leq\alpha(1+{4\delta})\frac{\left|T_{j}^{(\eta^{\prime})}\right|+\left|\overline{T_{j}}^{(\eta^{\prime})}\right|}{n}\mathbb{E}\left[\mathrm{Opt}(I)\right]+C\mathbb{E}\left[\mathrm{Opt}(I)\right]^{2/3}+o(\mathrm{Opt}(I))$
$\displaystyle\leq\alpha(1+{4\delta})\frac{\left|T_{j}^{(\eta^{\prime})}\right|+\frac{1}{\eta}\left|\overline{T_{j}}\right|}{n}\mathbb{E}\left[\mathrm{Opt}(I)\right]+C\mathbb{E}\left[\mathrm{Opt}(I)\right]^{2/3}+o(\mathrm{Opt}(I))$
$\displaystyle\leq\alpha(1+{4\delta})\frac{\left|T_{j}^{(\eta^{\prime})}\right|+\frac{1}{\eta}\left|\overline{T_{j}}\right|}{n}\mathbb{E}\left[\mathrm{Opt}(I)\right]+C\mathbb{E}\left[\mathrm{Opt}(I)\right]^{2/3}+o(\mathrm{Opt}(I))$
$\displaystyle\leq\alpha(1+{4\delta})\left(\frac{\left|T_{j}^{(\eta^{\prime})}\right|}{n}+\frac{1}{\eta}\right)\mathbb{E}\left[\mathrm{Opt}(I)\right]+C\mathbb{E}\left[\mathrm{Opt}(I)\right]^{2/3}+o(\mathrm{Opt}(I))$
(18)

The last inequality follows since $\left|\overline{T_{j}}\right|\leq n$.
Summing Equation 17 over $p\in[\eta^{\prime}-1]$ and Equation 18, and
observing that the number of chunks $\eta^{\prime}\leq\eta$ is a constant, we
get that with high probability, the number of bins used to pack the stage
$T_{j}$, say $A_{j}$ is bounded as follows.

$\displaystyle A_{j}$
$\displaystyle\leq\alpha(1+{4\delta})\left(\frac{\left|T_{j}\right|}{n}+\frac{1}{\eta}\right)\mathbb{E}\left[\mathrm{Opt}(I)\right]+\eta^{\prime}C\mathbb{E}\left[\mathrm{Opt}(I)\right]^{2/3}+o(\mathrm{Opt}(I))$
$\displaystyle\leq\alpha(1+{4\delta})\left(\frac{\left|T_{j}\right|}{n}+\delta\right)\mathbb{E}\left[\mathrm{Opt}(I)\right]+\eta
C\mathbb{E}\left[\mathrm{Opt}(I)\right]^{2/3}+o(\mathrm{Opt}(I))$ (19)

But note that when
$\left|T_{j}^{(\eta^{\prime})}\right|=\left|\overline{T_{j}}^{(\eta^{\prime})}\right|$,
Equation 17 holds for $p=\eta^{\prime}$ too. Then we obtain that

$\displaystyle
A_{j}\leq\alpha(1+{4\delta})\frac{\left|T_{j}\right|}{n}\mathbb{E}\left[\mathrm{Opt}(I)\right]+\eta
C\mathbb{E}\left[\mathrm{Opt}(I)\right]^{2/3}+o(\mathrm{Opt}(I))$ (20)

Notice that Equation 20 and Equation 12 (which represents the analysis of a
stage without chunking) are the same except for the constants in the lower
order terms. Hence, for all the super-stages (except for the last), we can
directly use the analysis of $\mathtt{Alg}$ as they are always full. For the
last stage in the last super-stage, we need to use Equation 19. For the other
stages in the last super-stage, we can use Equation 20 as they are always
full.

From now on, we will assume that the way in which $\mathtt{Alg}$ packs a stage
is tweaked in this manner.

Algorithm 3 $\mathtt{PackStage}$: Packing a stage $T_{j}$ ($j\geq 1$, i.e.,
$T_{j}$ is not the sampling stage)

1:Divide $\overline{T_{j}}$ into chunks
$\overline{T_{j}}^{(1)},\overline{T_{j}}^{(2)},\dots,\overline{T_{j}}^{(\eta)}$
of equal size.

2:$c_{j}\leftarrow$size of each chunk.

3:$k\leftarrow 1$$\triangleright$ The number of chunks of $\overline{T_{j}}$
processed

4:while stage $T_{j}$ doesn’t end do

5:
$D_{j}^{(k)}\leftarrow\overline{T_{j}}^{(k)};L\left(D_{j}^{(k)}\right)\leftarrow$
set of large items in $D_{j}^{(k)}$.

6: Pack $D_{j}^{(k)}$ by $\mathcal{A}_{\alpha}$; denote this packing by
$\mathcal{P}_{j}^{(k)}$$\triangleright$ The proxy packing

7: $\mathcal{S}_{j}^{(k)}\leftarrow\phi$$\triangleright$ the set of $S$-slots

8: for bin $B$ in $\mathcal{P}_{j}^{(k)}$ do

9: Remove the small items in $B$.

10: Create an $S$-slot $H$ of size equal to ($1-$weight of all the large items
in $B$).

11: $\mathcal{S}_{j}^{(k)}\leftarrow\mathcal{S}_{j}^{(k)}\cup H$

12: end for

13: $t\leftarrow 0$$\triangleright$ Number of items arrived for the current
chunk

14: while an item $x$ in $T_{j}$ arrives and $t\neq c_{j}$ do

15: if $x$ is large then

16: if $\exists d\in L\left(D_{j}^{(k)}\right)$ such that $d\geq x$ then

17: Find smallest such $d$.

18: $L\left(D_{j}^{(k)}\right)\leftarrow
L\left(D_{j}^{(k)}\right)\setminus\\{d\\}$.

19: Pack $x$ in place of $d$ in the packing $\mathcal{P}_{j}^{(k)}$.

20: else

21: Open a new bin and pack $x$ and close the bin.

22: end if

23: else

24: Try packing $x$ in $\mathcal{S}_{j}^{(k)}$ using Next-Fit.

25: if $x$ couldn’t be packed then

26: Open a new bin $B^{\prime}$ with a single $S$-slot of unit capacity.

27: $\mathcal{S}_{j}^{(k)}\leftarrow\mathcal{S}_{j}^{(k)}\cup B^{\prime}$.

28: Pack $x$ in $B^{\prime}$.

29: end if

30: end if

31: $t\leftarrow t+1$

32: end while

33: $k\leftarrow k+1$

34:end while

####  A.5.2 Analysis of $\mathtt{ImpAlg}$

Recall that the number of super-stages is given by
$\kappa=\left\lceil\log(n/n_{0})\right\rceil$ where $n_{0}$ was defined to be
$1/\delta^{3}$. We will split the analysis into two parts. First, we will
analyze the number of bins used by our algorithm in the first
$\kappa_{1}:=\left\lceil\log(\delta^{7}n)\right\rceil$ super-stages. Then, we
will analyze the final $\kappa_{2}:=\kappa-\kappa_{1}$ super-stages
considering one at a time. We call the first $\kappa_{1}$ super-stages as
_initial super-stages_ and the remaining $\kappa_{2}$ super-stages as _final
super-stages_.

Analysis of the initial super-stages: The basic intuition of the analysis of
our algorithm in the initial super-stages is as follows: Since only a small
fraction of the entire input is present in these $\kappa_{1}$ super-stages,
our algorithm uses only a small fraction of bins compared to the optimal
packing of the entire input. So, we bound the number of large items and the
weight of small items and thus bound the number of bins used.

######  Lemma A.1.

Let $\mathcal{A}$ be an algorithm for online bin packing such that in the
packing output by $\mathcal{A}$, every bin (except possibly a constant number
of bins $\mu$) which contains only small items has an occupancy of at least
$(1-\delta)$. Let $I$ be a sequence of $n$ i.i.d. items and let $J$ be the
prefix of $I$ having size $\beta n$ $(0<\beta\leq 1)$. Suppose $\mathcal{A}$
works in a way such that it packs at most $\nu$ copies of any large item where
$\nu$ is a constant333For example, $\mathtt{Alg}$ does this. Since it computes
proxy packing several times, potentially, several copies of a large item can
be packed. In the worst case, these copies may not get replaced, thus
resulting in wasted space.. Then the following inequality holds with high
probability.

$\displaystyle\mathcal{A}(J)\leq\frac{2\beta\nu}{\delta(1-\delta)}\mathbb{E}\left[\mathrm{Opt}(I)\right]+o(\mathbb{E}\left[\mathrm{Opt}(I)\right])$

######  Proof A.2.

Let $J_{\ell},I_{\ell}$ respectively denote the set of large items in $J,I$
and let $J_{s},I_{s}$ respectively denote the set of small items in $J,I$. We
prove the lemma considering two cases.

First, we consider the case when
$\left|J_{\ell}\right|\leq\delta\mathrm{Opt}(J)$. The number of bins in the
packing of $J$ by $\mathcal{A}$ which contain at least one large item is upper
bounded by $\nu\left|J_{\ell}\right|$. The number of bins which contain only
small items is upper bounded by $\mathcal{W}(J_{s})/(1-\delta)+\mu$. Hence,

$\displaystyle\mathcal{A}(J)$
$\displaystyle\leq\nu\left|J_{\ell}\right|+\frac{\mathcal{W}(J_{s})}{1-\delta}+\mu$
$\displaystyle\leq\nu\delta\mathrm{Opt}(J)+\frac{\mathrm{Opt}(J)}{1-\delta}+\mu$
$\displaystyle=\frac{1+\nu(1-\delta)\delta}{1-\delta}\mathrm{Opt}(J)+\mu$
$\displaystyle\leq 2\nu(1+\delta)\mathrm{Opt}(J)+\mu$ (since $0<\delta<1/2$
and $\nu\geq 1$) $\displaystyle\leq
2\beta\nu(1+\delta)(1+2\delta)\mathbb{E}\left[\mathrm{Opt}(I)\right]+C_{0}\mathbb{E}\left[\mathrm{Opt}(I)\right]^{2/3}\qquad\textrm{w.h.p.
for some constant $C_{0}$}$ (using Lemma 2.6)
$\displaystyle\leq\frac{2\beta\nu}{\delta(1-\delta)}\mathbb{E}\left[\mathrm{Opt}(I)\right]+o(\mathbb{E}\left[\mathrm{Opt}(I)\right])$
(since $\delta<1/2$, $1+\delta<\frac{1}{1-\delta}$ and
$1+2\delta<\frac{1}{\delta}$)

Next, we consider the case when $\left|J_{\ell}\right|>\delta\mathrm{Opt}(J)$.
We will again bound the quantity
$\nu\left|J_{\ell}\right|+\frac{\mathcal{W}(J_{s})}{1-\delta}+\mu$. To bound
$\left|J_{\ell}\right|$, we use Bernstein’s inequality (Lemma 2.2). Let
$X_{1},X_{2},\dots,X_{\left|J\right|}$ be random variables where $X_{i}$ takes
value $1$ if the $i^{\mathrm{th}}$ item in $J$ is large and $0$ otherwise.
Then, clearly, $\left|J_{\ell}\right|=\sum_{i=1}^{\left|J\right|}X_{j}$. Also,
note that
$\mathbb{E}\left[\left|J_{\ell}\right|\right]=\beta\mathbb{E}\left[\left|I_{\ell}\right|\right]$.
Moreover, we can derive the following inequalities that hold with high
probability.

$\displaystyle\mathbb{E}\left[\left|I_{\ell}\right|\right]$
$\displaystyle\geq\frac{1}{\beta}\left|J_{\ell}\right|-\frac{1}{\beta}\mathbb{E}\left[\mathcal{W}(I)\right]^{2/3}$
(using Lemma 2.5)
$\displaystyle\geq\frac{\delta}{\beta}\mathrm{Opt}(J)-\frac{1}{\beta}\mathbb{E}\left[\mathcal{W}(I)\right]^{2/3}$
$\displaystyle\geq\frac{\delta}{\beta}\mathcal{W}(J)-\frac{1}{\beta}\mathbb{E}\left[\mathcal{W}(I)\right]^{2/3}$
$\displaystyle\geq\frac{\delta}{\beta}\left(\beta\mathbb{E}\left[\mathcal{W}(I)\right]-\mathbb{E}\left[\mathcal{W}(I)\right]^{2/3}\right)-\frac{1}{\beta}\mathbb{E}\left[\mathcal{W}(I)\right]^{2/3}$
(using Lemma 2.4)
$\displaystyle\geq\frac{\delta}{2}\mathbb{E}\left[\mathrm{Opt}(I)\right]-o(\mathbb{E}\left[\mathrm{Opt}(I)\right])$
(since $\mathcal{W}(I)\leq\mathrm{Opt}(I)\leq 2\mathcal{W}(I)$)

Hence, from now on, we will assume that there exists a constant $a_{1}>0$ such
that

$\displaystyle\mathbb{E}\left[\left|I_{\ell}\right|\right]\geq
a_{1}\mathbb{E}\left[\mathrm{Opt}(I)\right]$ (21)

Using Bernstein’s inequality (Lemma 2.2),

$\displaystyle=$ $\displaystyle\leq
2\exp\left(-\frac{\beta^{2}\mathbb{E}\left[\left|I_{\ell}\right|\right]^{2}}{2\mathbb{E}\left[{\left|J_{\ell}\right|}\right]+\frac{2}{3}\beta\mathbb{E}\left[\left|I_{\ell}\right|\right]}\right)$
$\displaystyle=2\exp\left(-\frac{3}{8}\beta\mathbb{E}\left[\left|I_{\ell}\right|\right]\right)$
$\displaystyle\leq 2\exp\left(-\frac{3}{8}\beta
a_{1}\cdot\mathbb{E}\left[\mathrm{Opt}(I)\right]\right)$ (from Equation 21)

Now to bound $\mathcal{W}(J_{s})$, we will again use Bernstein’s inequality on
a new set of random variables $X_{1},X_{2},\dots,X_{\left|J\right|}$ where
$X_{i}$ equals the weight of the $i^{\mathrm{th}}$ item in $J$ if it is small
and $0$ otherwise. Clearly,
$\sum_{i=1}^{\left|J\right|}X_{i}=\mathcal{W}(J_{s})$ and
$\mathbb{E}\left[\mathcal{W}(J_{s})\right]=\beta\mathbb{E}\left[\mathcal{W}(I_{s})\right]\leq\beta\mathbb{E}\left[\mathcal{W}(I)\right]$.
Thus,

$\displaystyle\leq$ $\displaystyle\leq
2\exp\left(\frac{-\beta^{2}\mathbb{E}\left[\mathcal{W}(I)\right]^{2}}{2\mathbb{E}\left[{\mathcal{W}(J_{s})}\right]+\frac{2}{3}\beta\mathbb{E}\left[\mathcal{W}(I)\right]}\right)$
$\displaystyle=2\exp\left(\frac{-3\beta}{8}\mathbb{E}\left[\mathcal{W}(I)\right]\right)$
$\displaystyle\leq
2\exp\left(\frac{-3\beta\mathbb{E}\left[\mathrm{Opt}(I)\right]}{16}\right)$
(since $2\mathcal{W}(I)\geq\mathrm{Opt}(I)$)

Thus, with high probability, we have that $\left|J_{\ell}\right|\leq
2\beta\mathbb{E}\left[\left|I_{\ell}\right|\right]$ and
$\mathcal{W}(J_{s})\leq 2\beta\mathbb{E}\left[\mathcal{W}(I)\right]$. Hence,

$\displaystyle\mathcal{A}(J)$
$\displaystyle\leq\nu\left|J_{\ell}\right|+\frac{\mathcal{W}(J_{s})}{1-\delta}+\mu$
$\displaystyle\leq
2\nu\beta\mathbb{E}\left[\left|I_{\ell}\right|\right]+\frac{2\beta\mathbb{E}\left[\mathcal{W}(I)\right]}{1-\delta}+\mu$
$\displaystyle\leq\frac{2\nu\beta}{\delta}\mathbb{E}\left[\mathrm{Opt}(I)\right]+\frac{2\beta\mathbb{E}\left[\mathrm{Opt}(I)\right]}{1-\delta}+\mu$
$\displaystyle=\frac{2\nu\beta}{\delta(1-\delta)}\mathbb{E}\left[\mathrm{Opt}(I)\right]+o(\mathbb{E}\left[\mathrm{Opt}(I)\right])$

This completes the proof.

With the help of the above lemma, we proceed to analyze $\mathtt{ImpAlg}$ for
the initial (first $\kappa_{1}$) super-stages. Note that the number of items
in the initial super-stages is given by
$2^{\kappa_{1}-1}n_{0}\leq(\delta^{7}n_{0})n=\delta^{4}n$. Since
$\mathtt{Alg}$ satisfies the properties of $\mathcal{A}$ in Lemma A.1 and
$\mathtt{ImpAlg}$ just applies $\mathtt{Alg}$ multiple times, we can use Lemma
A.1 to analyze $\mathtt{ImpAlg}$.

There is one difficulty though. Let’s call a bin which contains only small
items to be an $S$-bin. Although in a super-stage the number of $S$-bins not
filled up to a level of at least $(1-\delta)$ is a constant, the number of
initial super-stages itself is not a constant. We can work around this problem
by continuing NF to pack the small items in the $S$-slots created during the
previous stages and the previous super-stages as well. In other words, instead
of packing the small items of a stage in $S$-slots created only during that
stage, we keep a global set of $S$-slots and pack the small items using NF. We
now have to show that our algorithm doesn’t increase the number of bins with
this change. Since the way in which the large items are packed hasn’t changed,
the number of bins that contain large items does not change. Since NF is
monotone (even with varying bin sizes, [37]), the number of bins containing
only the small items will either decrease or stays the same.

Hence, using Lemma A.1 with $\nu=1/\delta^{2}$ (since each super-stage
contains $1/\delta^{2}$ stages and so, each large item in this super-stage can
be packed at most $1/\delta^{2}$ times), we obtain that with high probability,

$\displaystyle\mathtt{Alg}(\Gamma_{0})+\mathtt{Alg}(\Gamma_{1})+\dots+\mathtt{Alg}(\Gamma_{\kappa_{1}-1})$
$\displaystyle\leq\frac{2(1/\delta^{2})\delta^{4}}{\delta(1-\delta)}\mathbb{E}\left[\mathrm{Opt}(I)\right]+o(\mathrm{Opt}(I))$
$\displaystyle\leq
4\delta\mathbb{E}\left[\mathrm{Opt}(I)\right]+o(\mathrm{Opt}(I))$ (22)

Analysis of the final super-stages: For this part, the important thing to note
is that $\kappa_{2}\leq\left\lceil\log(1/(\delta^{7}n_{0}))\right\rceil$ is a
constant. Moreover, since the number of items in the initial super-stages is
at least $\delta^{4}n/2$, each of the final super-stages has at least
$\delta^{4}n/2$ items (which tends to infinity in the limiting case). Thus, we
can use the analysis of $\mathtt{Alg}$ for each of these final super-stages.
As mentioned, since the last super-stage might not be full, we analyze the
last super-stage differently. All the other super-stages are full. So, we can
directly use the analysis of $\mathtt{Alg}$. For all $\kappa_{1}\leq
i<\kappa-1$, from the analysis of $\mathtt{Alg}$ (Equation 14), we have that
with high probability

$\displaystyle\mathtt{Alg}(\Gamma_{i})\leq\alpha(1+8\delta)\mathbb{E}\left[\mathrm{Opt}(\Gamma_{i})\right]+C\mathbb{E}\left[\mathrm{Opt}(\Gamma_{i})\right]^{2/3}+o(\mathrm{Opt}(\Gamma_{i}))$

for some constant $C$.

Now, to bound $\mathrm{Opt}(\Gamma_{i})$ in terms of $\mathrm{Opt}(I)$, we can
use Lemma 2.6. Thus, the above inequality transforms into

$\displaystyle\mathtt{Alg}(\Gamma_{i})$
$\displaystyle\leq\alpha(1+8\delta)(1+2\delta)\frac{\left|\Gamma_{i}\right|}{n}\mathbb{E}\left[\mathrm{Opt}(I)\right]+C_{1}\mathbb{E}\left[\mathrm{Opt}(\Gamma_{i})\right]^{2/3}+o(\mathrm{Opt}(\Gamma_{i}))$
$\displaystyle\leq\alpha(1+8\delta)(1+2\delta)\frac{\left|\Gamma_{i}\right|}{n}\mathbb{E}\left[\mathrm{Opt}(I)\right]+C_{1}\mathbb{E}\left[\mathrm{Opt}(I)\right]^{2/3}+o(\mathrm{Opt}(I))$

for some constant $C_{1}$. Summing over all $i$ $(\kappa_{1}\leq i<\kappa-1)$,
and observing that $\kappa-\kappa_{1}$ is a constant, we obtain that with high
probability,

$\displaystyle\mathtt{Alg}(\Gamma_{\kappa_{1}})+\mathtt{Alg}(\Gamma_{\kappa_{1}+1})+\dots+\mathtt{Alg}(\Gamma_{\kappa-2})$
$\displaystyle\leq$
$\displaystyle\alpha(1+8\delta)(1+2\delta)\sum_{i=\kappa_{1}}^{\kappa-2}\frac{\left|\Gamma_{i}\right|}{n}\mathbb{E}\left[\mathrm{Opt}(I)\right]+C_{2}\mathbb{E}\left[\mathrm{Opt}(I)\right]^{2/3}+o(\mathrm{Opt}(I))$
$\displaystyle\leq$
$\displaystyle\alpha(1+26\delta)\sum_{i=\kappa_{1}}^{\kappa-2}\frac{\left|\Gamma_{i}\right|}{n}\mathbb{E}\left[\mathrm{Opt}(I)\right]+C_{2}\mathbb{E}\left[\mathrm{Opt}(I)\right]^{2/3}+o(\mathrm{Opt}(I))$
(23)

for some constant $C_{2}$.

Now consider the last super-stage $\Gamma_{\kappa-1}$. If
$\left|\Gamma_{\kappa-1}\right|$ is exactly equal to $n_{k-1}-n_{k-2}$, then
we can obtain the same bound as Equation 23. However, this might not be the
case. So, we consider two cases. If we don’t go beyond the sampling stage of
the last-stage, i.e, if
$\left|\Gamma_{k-1}\right|\leq\delta^{2}(n_{k-1}-n_{k-2})$, then using Lemma
A.1 with $\nu=1$ (since we just use NF), we obtain that with high probability,

$\displaystyle\mathtt{Alg}(\Gamma_{\kappa-1})$
$\displaystyle\leq\frac{2\delta^{2}(n_{k-1}-n_{k-2})}{n\delta(1-\delta)}\mathbb{E}\left[\mathrm{Opt}(I)\right]+o(\mathbb{E}\left[\mathrm{Opt}(I)\right])$
$\displaystyle\leq
4\delta\mathbb{E}\left[\mathrm{Opt}(I)\right]+o(\mathbb{E}\left[\mathrm{Opt}(I)\right])$
(24)

where the last inequality follows from the facts that $\delta\leq 1/2$ and
$n\geq n_{k-1}-n_{k-2}$. On the other hand, if
$\left|\Gamma_{k-1}\right|>\delta^{2}2^{k-1}n_{0}$, then note that when
$\mathtt{Alg}$ was run on $\Gamma_{k-1}$, it must have completed the sampling
stage (since the size of the sampling stage is only
$\delta^{2}(n_{k-1}-n_{k-2})$) and proceeded into the remaining stages.

Let’s denote the number of bins used in the sampling stage of the last super-
stage by $A^{(\mathrm{samp})}_{\kappa-1}$ and the bins used in the remaining
stages by $A^{(\mathrm{rem})}_{\kappa-1}$. Using Lemma A.1 with $\nu=1$, with
high probability, we can bound $A^{(\mathrm{samp})}_{\kappa-1}$:

$\displaystyle A^{(\mathrm{samp})}_{\kappa-1}$
$\displaystyle\leq\frac{2\delta^{2}(n_{k-1}-n_{k-2})}{n\delta(1-\delta)}\mathbb{E}\left[\mathrm{Opt}(I)\right]+o(\mathbb{E}\left[\mathrm{Opt}(I)\right])$
$\displaystyle\leq{4\delta}\mathbb{E}\left[\mathrm{Opt}(I)\right]+o(\mathbb{E}\left[\mathrm{Opt}(I)\right])$

Let the number of stages in the last super-stage be $\tau$. Let
$\Gamma_{\kappa-1}^{(j)}$ denote the set of items in the $j^{\mathrm{th}}$
stage of the super-stage $\Gamma_{\kappa-1}$. For each $j\in[\tau-1]$, we can
use Equation 20 to bound the number of bins used for packing
$\Gamma_{\kappa-1}^{(j)}$. For $\Gamma_{\kappa-1}^{(\tau)}$, we can use
Equation 19 to bound the number of bins. Thus, with high probability, for some
constant $C_{3}$, we obtain that

$\displaystyle A^{(\mathrm{rem})}_{\kappa-1}$
$\displaystyle\leq\alpha(1+{4\delta})\left(\sum_{j=1}^{\tau-1}\frac{\left|\Gamma_{\kappa-1}^{(j)}\right|}{n}+\left(\frac{\left|\Gamma_{\kappa-1}^{(\tau)}\right|}{n}+\delta\right)\right)\mathbb{E}\left[\mathrm{Opt}(I)\right]$
$\displaystyle\>\>+C_{3}\mathbb{E}\left[\mathrm{Opt}(I)\right]^{2/3}+o(\mathrm{Opt}(I))$
$\displaystyle\leq\alpha(1+4\delta)\left(\frac{\left|\Gamma_{\kappa-1}\right|}{n}+\delta\right)\mathbb{E}\left[\mathrm{Opt}(I)\right]+C_{3}\mathbb{E}\left[\mathrm{Opt}(I)\right]^{2/3}+o(\mathrm{Opt}(I))$

Hence, the total number of bins used by $\mathtt{ImpAlg}$ for the last super-
stage $A^{(\mathrm{samp})}_{\kappa-1}+A^{(\mathrm{rem})}_{\kappa-1}$ can be
bounded as

$\displaystyle\mathtt{Alg}\left(\Gamma_{\kappa-1}\right)$
$\displaystyle\leq\alpha(1+4\delta)\left(\frac{\left|\Gamma_{\kappa-1}\right|}{n}+5\delta\right)\mathbb{E}\left[\mathrm{Opt}(I)\right]+C_{3}\mathbb{E}\left[\mathrm{Opt}(I)\right]^{2/3}+o(\mathrm{Opt}(I))$
$\displaystyle\leq\alpha(1+26\delta)\left(\frac{\left|\Gamma_{\kappa-1}\right|}{n}+5\delta\right)\mathbb{E}\left[\mathrm{Opt}(I)\right]+C_{3}\mathbb{E}\left[\mathrm{Opt}(I)\right]^{2/3}+o(\mathrm{Opt}(I))$
(25)

It can be seen that among Equation 25 and Equation 24, the former (i.e., when
we complete the sampling stage of the last super-stage) represents the worst
case scenario.

Summing Equations 22, 23 and 25, we obtain that with high probability, for
some constant $C_{4}$,

$\displaystyle\mathtt{ImpAlg}\left(I\right)$
$\displaystyle=\sum_{j=0}^{\kappa_{1}-1}\mathtt{Alg}(\Gamma_{j})+\sum_{j=\kappa_{1}}^{\kappa-2}\mathtt{Alg}(\Gamma_{j})+\mathtt{Alg}(\Gamma_{\kappa-1})$
$\displaystyle\leq\left(4\delta+\alpha(1+26\delta)\left(\sum_{i=\kappa_{1}}^{\kappa-2}\frac{\left|\Gamma_{i}\right|}{n}+\frac{\left|\Gamma_{\kappa-1}\right|}{n}+5\delta\right)\right)\mathbb{E}\left[\mathrm{Opt}(I)\right]$
$\displaystyle\qquad\qquad\qquad+C_{4}\mathbb{E}\left[\mathrm{Opt}(I)\right]^{2/3}+o(\mathrm{Opt}(I))$
$\displaystyle\leq\left(4\delta+\alpha(1+26\delta)\left(1+5\delta\right)\right)\mathbb{E}\left[\mathrm{Opt}(I)\right]$
$\displaystyle\qquad\qquad\qquad+C_{4}\mathbb{E}\left[\mathrm{Opt}(I)\right]^{2/3}+o(\mathrm{Opt}(I))$
$\displaystyle\leq\alpha\left(1+165\delta\right)\mathbb{E}\left[\mathrm{Opt}(I)\right]$
$\displaystyle\qquad\qquad\qquad+C_{4}\mathbb{E}\left[\mathrm{Opt}(I)\right]^{2/3}+o(\mathrm{Opt}(I))$
(26)

Equation 26 holds with high probability, say $p=1-o(1)$. In the scenario where
the low probability event occurs, we can bound the number of bins used by
$\mathtt{ImpAlg}$ using Lemma A.1 with $\beta=1$ and $\nu=1/\delta^{2}$:

$\displaystyle\mathtt{ImpAlg}(I)\leq\frac{2(1/\delta^{2})}{\delta(1-\delta)}\mathbb{E}\left[\mathrm{Opt}(I)\right]+o(\mathbb{E}\left[\mathrm{Opt}(I)\right])$

Let $E$ be the event when Equation 26 holds. Then

$\displaystyle\mathbb{E}\left[\mathtt{ImpAlg}(I)\right]$
$\displaystyle=\mathbb{E}\left[\mathtt{ImpAlg}(I)|E\right]$
$\displaystyle\leq\Big{(}\left(\alpha\left(1+165\delta\right)\right)\mathbb{E}\left[\mathrm{Opt}(I)\right]+o(\mathbb{E}\left[\mathrm{Opt}(I)\right])\Big{)}(1-o(1))$
$\displaystyle\>\>\>\>\>\>+\left(\frac{2}{\delta^{3}(1-\delta)}\mathbb{E}\left[\mathrm{Opt}(I)\right]+1\right)o(1)$
$\displaystyle=\left(\alpha\left(1+165\delta\right)\right)\mathbb{E}\left[\mathrm{Opt}(I)\right]+o(\mathbb{E}\left[\mathrm{Opt}(I)\right]$

Choosing $\delta=\frac{\varepsilon}{165\alpha}$ ensures that the competitive
ratio of $\mathtt{ImpAlg}$ is $\alpha+\varepsilon$.

##  Appendix B Details of Section 3.2

######  Proof B.1 (Proof of 18).

One can construct a random permutation of the input list $I$ by first placing
the small items in a random order and then inserting the remaining items among
the small items randomly.

After placing the small items, we have $m+1$ gaps to place the remaining items
as shown below in the form of empty squares.

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

As shown above, we name the $S$-triplets as $T_{1},T_{2},\dots,T_{m/3}$
(Strictly speaking, the number of $S$-triplets should be $\left\lfloor
m/3\right\rfloor$, but we relax this since we are only interested in the
asymptotic case and $m\geq cn$). Let us start inserting the non-small items
into these empty squares. Consider any $S$-triplet $T_{i}$. The probability
that $T_{i}$ continues to be an $S$-triplet after inserting the first non-
small item is $(m-1)/(m+1)$. The first non-small item thus occupies one of the
squares, but in this process, it creates two new squares on either side of
itself, thereby increasing the net number of squares by one. Hence, the
probability that $T_{i}$ continues to be an $S$-triplet after inserting the
second non-small item (given it remains to be one after inserting the first
non-small item) is $m/(m+2)$. We continue this process of inserting the non-
small items and after they all have been inserted, let $Y_{\sigma}^{(i)}$ be
the indicator random variable denoting whether $T_{i}$ is consecutive or not.
Then

$\displaystyle\mathbb{E}\left[Y_{\sigma}^{(i)}\right]=\frac{m-1}{m+1}\frac{m}{m+2}\cdots\frac{n-2}{n}=\frac{m(m-1)}{n(n-1)}.$

Let $Y_{\sigma}=Y_{\sigma}^{(1)}+Y_{\sigma}^{(2)}+\dots+Y_{\sigma}^{(m/3)}$,
by linearity of expectations,

$\displaystyle\lim_{n,m\to\infty}\mathbb{E}\left[Y_{\sigma}\right]=\lim_{n,m\to\infty}\frac{m}{3}\frac{m(m-1)}{n(n-1)}{\approx\frac{m^{3}}{3n^{2}}\geq\frac{c^{3}n}{3}}.$

Since $X_{\sigma}\geq Y_{\sigma}$, the first part of the claim follows.

To prove the second part of the claim, we will compute
$\mathrm{Var}\left[Y_{\sigma}\right]$ and use Chebyshev’s inequality. For any
$i$,

$\displaystyle\mathrm{Var}\left[Y_{\sigma}^{(i)}\right]$
$\displaystyle=\mathbb{E}\left[Y_{\sigma}^{(i)}\right]-\mathbb{E}\left[Y_{\sigma}^{(i)}\right]^{2}$
$\displaystyle=\frac{m(m-1)}{n(n-1)}-\frac{m^{2}(m-1)^{2}}{n^{2}(n-1)^{2}}$
$\displaystyle=\frac{m(m-1)(n-m)(n+m-1)}{n^{2}(n-1)^{2}}$ $\displaystyle\leq
2$ (27)

Now, consider any two $S$-triplets $T_{j},T_{k}$. The probability that both
$T_{j}$ and $T_{k}$ remain to be $S$-triplets after inserting the first non-
small item is $(m-3)/(m+1)$. Continuing in this manner, after all the non-
small items have been inserted,

$\mathbb{E}\left[Y_{\sigma}^{(j)}Y_{\sigma}^{(k)}\right]=$

The covariance of $Y_{\sigma}^{(j)},Y_{\sigma}^{(k)}$ is given by

$\displaystyle\mathrm{Cov}\left[Y_{\sigma}^{(j)},Y_{\sigma}^{(k)}\right]$
$\displaystyle=\mathbb{E}\left[Y_{\sigma}^{(j)}Y_{\sigma}^{(k)}\right]-\mathbb{E}\left[Y_{\sigma}^{(j)}\right]\mathbb{E}\left[Y_{\sigma}^{(k)}\right]$
$\displaystyle=\frac{m(m-1)(m-2)(m-3)}{n(n-1)(n-2)(n-3)}-\frac{m^{2}(m-1)^{2}}{n^{2}(n-1)^{2}}$
$\displaystyle=\frac{m(n-m)(m-1)(4nm-6m-6n+6)}{n^{2}(n-1)^{2}(n-2)(n-3)}$
$\displaystyle\leq\frac{4n^{3}(n-1)^{2}}{n^{2}(n-1)^{2}(n-2)(n-3)}$
$\displaystyle=\frac{4n}{(n-2)(n-3)}$ $\displaystyle\leq\frac{6}{n}$ (28)

Combining all these, the variance of $Y_{\sigma}$ can be calculated as follows

$\displaystyle\mathrm{Var}\left[Y_{\sigma}\right]$
$\displaystyle=\sum_{i=1}^{m/3}\mathrm{Var}\left[Y_{\sigma}^{(i)}\right]+2\sum_{1\leq
j<k\leq m/3}\mathrm{Cov}\left[Y_{\sigma}^{(j)},Y_{\sigma}^{(k)}\right]$
$\displaystyle\leq\frac{2m}{3}+\frac{m}{3}\left(\frac{m}{3}-1\right)\frac{6}{n}$
(from Equations 27 and 28) $\displaystyle\leq 2n$

Now using Chebyshev’s inequality,

$\displaystyle\leq$
$\displaystyle\leq\frac{\mathrm{Var}\left[Y_{\sigma}\right]}{\left(\mathbb{E}\left[Y_{\sigma}\right]\right)^{4/3}}$
$\displaystyle\leq\frac{2n}{\frac{c^{4}}{3^{4/3}}n^{4/3}}$
$\displaystyle=O\left(\frac{1}{n^{1/3}}\right),\text{as $c$ is a constant.}$

Since $X_{\sigma}$ is the maximum number of $S$-triplets, $X_{\sigma}\geq
Y_{\sigma}\geq c^{3}n/3-o(n)$ with high probability.

######  Proof B.2 (Proof of 19).

There are three cases we need to consider.

  * •

If $S_{1}$ is going to be packed in a $2$-bin. Then after packing $S_{1}$,
this bin becomes a $3$-bin and hence the claim holds.

  * •

Suppose $S_{1}$ is going to be packed in a $1$-bin $B$. Then just before the
arrival of $S_{1}$, $B$ must have been the only $1$-bin and hence, after
packing $S_{1}$, each bin is either a $2$-bin or a $3$-bin.

    * –

Now, if one of $S_{2},S_{3}$ is packed into a $2$-bin, then the bin becomes a
$3$-bin and the claim follows.

    * –

Otherwise, both $S_{2},S_{3}$ are packed into a single new $SS$-bin and hence
the claim follows.

  * •

Suppose $S_{1}$ is packed in a new bin. Then just prior to the arrival of
$S_{2}$, every bin is either a $2$-bin or $3$-bin except the bin containing
$S_{1}$. Thus, $S_{2}$ is either packed in a $2$-bin (thus becoming a $3$-bin)
or packed in the bin containing $S_{1}$, resulting in an $SS$-bin.

Now we prove Theorem 1.4.

######  Proof B.3 (Proof of Theorem 1.4).

Consider the final Best-Fit packing of $I_{\sigma}$. Let $X_{3}$ be the number
of $3$-bins. The remaining $(n-3X_{3})$ items are packed in $2$-bins and at
most one $1$-bin. Therefore,

$\mathrm{BF}(I_{\sigma})\leq
X_{3}+\frac{n-3X_{3}}{2}+1=\frac{n-X_{3}}{2}+1\leq\frac{3}{2}\left(1-\frac{X_{3}}{n}\right)\mathrm{Opt}(I_{\sigma})+1$
(29)

The last inequality follows from the fact that any bin in the optimal solution
can accommodate at most three items. Let $z_{1}(\leq 1),z_{2}$ and $z_{3}$ be
the number of $1$-bins, $2$-bins and $3$-bins in the optimal packing of
$I_{\sigma}$, respectively. Then, $\mathrm{Opt}(I_{\sigma})=z_{1}+z_{2}+z_{3}$
and $n=z_{1}+2z_{2}+3z_{3}$. Note that any two items can fit in a bin.
Therefore,

$\mathrm{BF}(I_{\sigma})\leq\frac{n+1}{2}=\frac{z_{1}+2z_{2}+3z_{3}+1}{2}\leq\frac{3\mathrm{Opt}(I_{\sigma})-z_{2}-2z_{1}+1}{2}\leq\left(\frac{3}{2}-\frac{\mu}{2}\right)\mathrm{Opt}(I_{\sigma})+1$
(30)

where $\mu:={z_{2}}/{\mathrm{Opt}(I_{\sigma})}$ is the fraction of $2$-bins in
the optimal solution.

When $\mu$ is close to one (say $\mu>0.999$), we already obtain a competitive
ratio very close to $1$ due to the above inequality. When $\mu\leq 0.999$,
then $m$, the number of small items in the input list is at least $0.00033n$.
This is because $z_{3}$, the number of $3$-bins in the optimal solution, is at
least $0.001\mathrm{Opt}(I_{\sigma})-1\geq 0.001(n/3)-1\geq 0.00033n$ and any
$3$-bin must contain at least one small item.

Hence, assuming $\mu\leq 0.999$, let us analyze the Best-Fit packing of
$I_{\sigma}$ in a different way. Let $n_{s}$ be the number of small items.
Since a $3$-bin contains at least one small item, we know that, $n_{s}\geq
z_{3}\geq(1-\mu)\mathrm{Opt}(I_{\sigma})-z_{1}$. Let $X_{\sigma}$ be the
random variable which denotes the maximum number of $S$-triplets in the input
sequence. By 18,

$X_{\sigma}\geq\frac{((1-\mu)\mathrm{Opt}(I_{\sigma})-z_{1})^{3}}{3n^{2}}-o(n)\approx\frac{(1-\mu)^{3}\mathrm{Opt}(I_{\sigma})^{3}}{3n^{2}}-o(n){\text{
w.h.p.}},\text{ as }z_{1}\leq 1.$

In the Best-Fit solution, the number of $SS$-bins can at most be one. Hence,
by 19,

$X_{3}\geq\frac{X_{\sigma}}{3}-1\geq\frac{(1-\mu)^{3}\mathrm{Opt}(I_{\sigma})^{3}}{9n^{2}}-o(n)\geq\frac{(1-\mu)^{3}n}{243}-o(n){\text{
w.h.p.}}$

The last inequality follows from the fact that $\mathrm{Opt}(I_{\sigma})\geq
n/3$. Using Equation 29, we get,

$\displaystyle\mathrm{BF}(I_{\sigma})$
$\displaystyle\leq\frac{3}{2}\left(1+\frac{o(n)}{n}-\frac{(1-\mu)^{3}}{243}\right)\mathrm{Opt}(I_{\sigma})+1$
$\displaystyle\leq\frac{3}{2}\left(1-\frac{(1-\mu)^{3}}{243}\right)\mathrm{Opt}(I_{\sigma})+o(\mathrm{Opt}(I_{\sigma})){\text{
w.h.p.}}$ (31)

Equations 30 and 31 are the result of two different ways of analyzing the same
algorithm. Hence, the expected competitive ratio is given by
$\min\left\\{\frac{3}{2}-\frac{\mu}{2},\frac{3}{2}-\frac{(1-\mu)^{3}}{162}\right\\}$.
When both the above quantities are equal, we obtain the worst-case competitive
ratio. This happens when $81\mu=(1-\mu)^{3}$, i.e., $\mu\approx 0.01191$; the
approximation ratio, in this case, is roughly $1.494045$.

We just proved that with high probability, say $p=1-o(1)$, $\mathrm{BF}(I)\leq
1.494045\mathrm{Opt}(I)+o(\mathrm{Opt}(I))$. The fact that $\mathrm{BF}(I)\leq
1.7\mathrm{Opt}(I)+2$ always holds due to [28]. Combining both these,
$\mathbb{E}\left[\mathrm{BF}(I)\right]\leq
p(1.494045\mathbb{E}\left[\mathrm{Opt}(I)\right]+o(\mathbb{E}\left[\mathrm{Opt}(I)\right]))+(1-p)(1.7\mathbb{E}\left[\mathrm{Opt}(I)\right]+2)$.
Thus we obtain that $\mathbb{E}\left[\mathrm{Opt}(I)\right]\leq
1.494045\mathbb{E}\left[\mathrm{Opt}(I)\right]+o(\mathbb{E}\left[\mathrm{Opt}(I)\right])$.

This completes the proof of Theorem 1.4.

##  Appendix C Multidimensional Online Vector Packing Problem under i.i.d.
model

In this section, we design an algorithm for $d$-dimensional online vector
packing problem (d-OVP) where $d$ is a positive integer constant. In this
entire section, we abbreviate a tuple with $d$ entries as just _tuple_. A
tuple $Y$ is represented as $\left(Y^{(1)},Y^{(2)},\dots,Y^{(d)}\right)$. We
define $Y^{\max}$ to be $\max\left\\{Y^{(1)},Y^{(2)},\dots,Y^{(d)}\right\\}$
In d-OVP, the input set $I$ consists of $n$ tuples $X_{1},X_{2},\dots,X_{n}$
which arrive in online fashion; we assume that $n$ is known beforehand. Each
$X_{i}^{(j)}$ is sampled independently from a distribution
$\mathcal{D}^{(j)}$. The objective is to partition the $n$ tuples into a
minimum number of bins such that for any bin $B$ and any $j\in[d]$, the sum of
all the $j^{\mathrm{th}}$ entries of all the tuples in $B$ does not exceed
one. Formally, we require that for any bin $B$ and any $j\in[d]$,$\sum_{x\in
B}x^{(j)}\leq 1$.

###  C.1 Algorithm

Given an offline $\alpha$-asymptotic approximation algorithm
$\mathcal{A}_{\alpha}$ for bin packing, we obtain a
$(d\alpha+\varepsilon)$-competitive algorithm for d-OVP as follows: For every
input tuple $X_{i}$, we round each $X_{i}^{(j)},j\in[d]$ to $X_{i}^{\max}$.
After rounding, since all the tuples have same values in each of the $d$
entries, we can treat each tuple $X_{i}$ as an one-dimensional item of size
$X_{i}^{\max}$.

It is easy to see that each $X_{i}^{\max}$ is independently sampled from the
same distribution: Let $F^{(j)}$ be the cumulative distribution function (CDF)
of $\mathcal{D}^{(j)}$. Then the CDF, $F$, of $X_{i}^{\max}$ (for any
$i\in[n]$) is given by

$\displaystyle F(y)=$ $\displaystyle=\prod_{j=1}^{d}$ (By independence of
$X_{i}^{(j)}$s) $\displaystyle=\prod_{j=1}^{d}F^{(j)}(y)$

Hence, the problem at hand reduces to solving an online bin packing problem
where items are independently sampled from a distribution whose CDF is given
by the function $\prod_{i=1}^{d}F^{(j)}$. So, we can use the algorithm from
Section 2.

###  C.2 Analysis

Let $I$ denote the vector packing input instance and let $\overline{I}$ denote
the rounded up one-dimensional bin packing instance.

######  Lemma C.1.

Let $\mathrm{Opt}_{v}(I)$ denote the optimal number of bins used to pack $I$.
Then $\mathrm{Opt}(\overline{I})\leq d\mathrm{Opt}_{v}(I)$.

######  Proof C.2.

Consider any optimal packing of $I$. We show how to construct a feasible
packing of $\overline{I}$ starting from the optimal packing of $I$. Consider
any bin in the optimal packing of $I$ and let $B$ denote the set of tuples
packed inside it. Let $\overline{B}$ denote the rounded-up instance of $B$.
Also, for $j\in[d]$, let $B^{(j)}$ denote the set of tuples whose
$j^{\mathrm{th}}$ dimension has the largest weight, i.e.,

$\displaystyle B^{(j)}=\left\\{Y\in B:Y^{(j)}=Y^{\max}\right\\}$

If any tuple belongs to $B^{(j)}$ as well as $B^{(k)}$ for some $j\neq k$, we
break these ties arbitrarily and assign it to one of $B^{(j)},B^{(k)}$. For
$j\in[d]$, let $\overline{B^{(j)}}$ denote the rounded instance of $B^{(j)}$.
We can pack $\overline{B}$ in at most $d$ bins as follows: For any $j\in[d]$,
we know that

$\displaystyle\sum_{Y\in B^{(j)}}Y^{(j)}\leq 1$

and since for all $Y\in B^{(j)}$, $Y^{\max}=Y^{(j)}$, it follows that

$\displaystyle\sum_{Z\in\overline{B^{(j)}}}Z\leq 1$

Hence, we can pack every $\overline{B^{(j)}}$ in one bin and the lemma
follows.

Now we are ready to prove our main theorem of this section.

######  Theorem C.3.

For any $\varepsilon>0$ and a given polynomial-time $\alpha$-approximation
algorithm for online bin packing, we can obtain a polynomial-time algorithm
for d-OVP with an asymptotic approximation ratio of $(\alpha d+\varepsilon
d)$.

######  Proof C.4.

Let us denote our present algorithm by $\mathtt{Alg}_{v}$. Then we get:

$\displaystyle\mathtt{Alg}_{v}(I)$ $\displaystyle=\mathtt{Alg}(\overline{I})$
(32)
$\displaystyle\leq(\alpha+\varepsilon)\mathrm{Opt}(\overline{I})+o\left(\mathrm{Opt}(\overline{I})\right)$
(33) $\displaystyle\leq(\alpha d+\varepsilon
d)\mathrm{Opt}_{v}(I)+o(\mathrm{Opt}_{v}(I)).$ (34)

Here, Equation (32) follows from the property of $\mathtt{Alg}_{v}$, (33)
follows from the results of Section 2, and (34) follows from Lemma C.1. This
concludes the proof.