Lower Bounds for Several Standard Bin Packing Algorithms in the Random Order Model

The Best Fit (BF) algorithm [31, 20, 38] is defined as follows. It starts with an empty set of active bins. Whenever a new item is revealed, it computes the subset of active bins in which the new item can be added without exceeding the bound of $1$ on the total size of items including the new item. If this subset is non-empty, the algorithm picks a bin of maximum total size of items from the subset and packs the item there. If the subset is empty, it opens a new (empty) bin that is defined as an active bin and it packs the item there. The asymptotic (and absolute) asymptotic approximation ratio of BF is $1.7$ [31, 20].

In addition to BF, we analyze two well-studied bounded space algorithms, namely $2$-BF and $2$-FF. Bounded space algorithms also have an active set of bins, but their number is bounded from above by a constant integer parameter. Thus, a bounded space algorithm may close a bin in order to open a new active bin, in which case the closed bin cannot be used again. Next Fit (NF) [30] is a greedy bounded space algorithm that has at most one active bin. If it has no active bin, NF opens a new bin which becomes active, and the item is packed into that bin. If NF has an active bin and the item can be packed into that bin with respect to its size, this is done. Otherwise, if there is an active bin, it is closed, and a new bin is opened, such that it receives the new item and becomes active.

Bounded space algorithms with larger numbers of active bins were studied as well [36, 43, 41, 40, 18, 44, 42]. The algorithm $2$-BF has at most two active bins at all times, and initially it has no active bins. When a new item is presented, it is packed into an active bin with the maximum already packed total size (where it fits). If this is not possible and the number of active bins is $2$, the most loaded active bin is closed (and it will not be able to receive new items), and (no matter whether a bin was closed or not) a new active bin is opened for the new item. A related algorithm is called $2$-FF, and the difference is that in the case where there are two active bins such that each one of them can receive the new item, the bin that was opened first is used (and not the fullest bin). The latter algorithm can be seen as the bounded space version of First Fit (FF) [31], which packs every item into the bin of minimum index where it can be added. The two algorithms were analyzed with respect to the worst-case asymptotic approximation ratio. The asymptotic approximation ratio of $2$-BF is $1.7$ [19], as for BF (and FF) [31, 20], and the asymptotic approximation ratio of $2$-FF is $2$ (as for NF) [40, 44].

The random order model was introduced for comparison and for contrast with worst-case analysis. In this model, the expected cost or profit over all permutations for an input is compared to the optimal offline cost or profit. For bin packing, this means that all $n!$ permutations of a set of $n$ items are considered with a uniform distribution over the permutations (which are input sequences). For an offline optimal solution, there is no meaning to the permutation, since the input of an offline bin packing algorithm is a set of items rather than a sequence. Such inputs were studied for various problems such as graph coloring [10, 25] and scheduling [2, 1], and other problems [33, 39, 14, 35, 27, 4, 28, 26]. Here, we study it with respect to bin packing [34, 16, 3, 5, 29]. We follow previous work and use a stochastic process for presenting lower bounds on the performance guarantee in the random order model. This stochastic process is a Markov chain with a finite number of states whose transition probabilities are provided by the family of permutations of a common set of items. This Markov chain allows us to compute the equilibrium probabilities of the states using standard approaches, and these equilibrium probabilities allow us to find the resulting lower bound in a straightforward computation. Thus, the crux is to define the input set of items and the corresponding set of states and transition probabilities of the Markov chain. Note that a related model where algorithms are compared directly based on inputs with their random permutations and not with comparison to an optimal offline solution was studied for several problems including bin packing [11, 21, 15, 13, 12].

Kenyon [34] started the study of BF with respect to randomly ordered inputs. She proved a lower bound of approximately $1.08$ on the asymptotic approximation ratio of BF with randomly ordered inputs, and wrote that $1.15$ may be a lower bound. Many years later, Albers, Khan, and Ladewig [3] improved the lower bound to $1.1037$, and finally Hebbar, Khan, and Sreenivas [29] improved the lower bound to $1.144$. Kenyon [34] also proved the surprising result that the asymptotic approximation ratio of BF in this model is at most $1.5$. By using various ingredients, this result was improved to slightly below $1.5$ [29]. For the special case of items of sizes in $(\frac{1}{4},\frac{1}{2}]$, an upper bound of approximately $1.4941$ on the asymptotic approximation ratio of BF for randomly ordered inputs was shown [5].

Randomly ordered inputs with items larger than $1/3$ (inputs with large items) were studied by Albers, Khan, and Ladewig [3], who showed that the asymptotic approximation for this case is at most $1.25$. It was proved afterwards [5] that the asymptotic approximation ratio for this case is in fact $1$. Interestingly, the absolute ratio for general inputs and even for inputs with large items is not $1$. Lower bounds of $1.3$ and $1.2$, respectively, were shown [3] for the absolute approximation ratio for general inputs and for items of sizes above $\frac{1}{3}$, respectively (where for the last case an upper bound of $\frac{21}{16}=1.3125$ on the absolute approximation ratio of BF was proved in the same work).

Coffman et al. analyzed NF for BP with random order [16], and showed that the asymptotic competitive ratio is unchanged (as opposed to the situation with BF [34]). The main idea for the lower bound proof is to use the worst-case input of NF that alternates between items of size $\frac{1}{2}$ and very small items of size $\mathrm{\epsilon }>0$. It is possible to add multiple items of size $\mathrm{\epsilon }$ instead of just one between every two items of size $\frac{1}{2}$, and applying NF on almost every permutation of this input will result in bins with one item of size $\frac{1}{2}$ and many items of size $\mathrm{\epsilon }$, and a very small number of bins with two items of size $\frac{1}{2}$.

Bin packing has different variants. A dual problem to BP is bin covering (BC) (see for example [13, 22, 23]), which is a maximization problem. BC can also be offline or online. The input is the same as for bin packing, but subsets should be covered in the sense that total sizes of bins that count towards the objective should be at least $1$. Bin covering and other related problems were studied with respect to inputs permuted in a random order [13, 22, 23, 24]. Fischer [24] presented algorithms of asymptotic approximation ratios that are $1$ or close to $1$ using definitions of the analysis of the type that we perform here, though those are not natural algorithms, and they are randomized.

We provide lower bounds on the asymptotic approximation ratio for three online algorithms for standard bin packing. Two of these algorithms are the bounded space algorithms $2$-BF and $2$-FF, and the third algorithm is BF, which was already studied with respect to random orders. We provide an improved lower bound for BF, and much higher lower bounds for algorithms whose performance is the same as BF ($2$-BF) and not much worse than BF ($2$-FF) in terms of worst-case analysis. Our lower bound for Best Fit is $1.15582656$, while the previous bound was $1.1440$ [29]. Our lower bound for $2$-BF is $\frac{4}{3}$, and our lower bound for $2$-FF is above $1.41$. The last two bounds for the bounded space algorithms are based on common input sets of items. We start our study by considering this type of input and the resulting bounds for $2$-BF and $2$-FF in Section 2. Then, we turn our attention to BF, and present our lower bound in Section 3. Our lower bound for the asymptotic approximation ratio of BF is based on Markov chains on finite sets of item sizes (and so are the other lower bounds). The cardinalities of the sets of item sizes are (positive) integer parameters of our construction. Previous lower bounds for BF were also based on the approach of Markov chains [34, 3, 29] (as described above), but there was a single (constant cardinality) set of items for each proof (with at least two and at most seven item sizes) rather than a class of sets of sizes. Our lower bound for BF holds even for items of sizes in $(\frac{1}{4},\frac{1}{2}]$, which is the special case that was studied by Ayyadevara et al. [5] with respect to an upper bound for BF, while the current best lower bound for this special case is the one of Kenyon [34]. In Section 4, we prove a new lower bound on the absolute approximation ratio of BF for randomly ordered inputs, improving the lower bound of $1.3$ [3] to $1.5$. A forthcoming full version will contain additional details and omitted proofs.

For patterns with three items the claim holds since there are no patterns with four items. For patterns with two items the claim holds by Lemma 4 since there is no valid pattern containing such a pair of items and an additional item. $◀$

Thus, bins that are not ready are those with a single item, with two items smaller than $\frac{1}{3}$, and with a pair of items of sizes $U_{j_1},V_{j_2}$ such that $j_2\ge j_1$. The following lemma establishes that although BF is not a bounded space algorithm, when we restrict our attention to this class of inputs, BF is in fact bounded space.

The claim holds for bins with a single item since any two items can be packed into a bin together and BF does not open a new bin when it can pack an item into an existing bin.

Assume that there are two bins with one or two items smaller than $\frac{1}{3}$ packed into each of these bins. When the second one of these bins was opened, its first item could have been packed into the first one of these two bins, while BF does not open a new bin when it can pack an item into an existing bin.

Finally, consider two bins, each with a pair of items of sizes $U_{j_1},V_{j_2}$ such that $j_2\ge j_1$. When the second such bin is opened, the first such bin already has two items, since any two items can be packed together into a bin. When the item of size $U_{j_1}$ of the second bin arrives, its bin has at most one item. Thus, the first bin has a total size $U_{j_1}+V_{j_2}$ while the second bin has at most $V_{j_2}$. Since a pattern with one item of size $V_{j_2}$ and two items of size $U_{j_1}$ is valid, the item of size $U_{j_1}$ should have preferred to be packed into the first bin by BF. $◀$

We use the following names for bins that are not ready.

• $\mathrm{■}$

  A bin with a single item is called $OH$ if it has an item of size $Z$, it is called $O{S}_i$ if it has an item of size $U_i$ and it is called $O{L}_i$ if it has an item of size $V_i$. Recall that there is at most one such bin (out of all $2k+1$ types for such a bin) at every time.

• $\mathrm{■}$

  A bin with two items of sizes $U_{j_1}$ and $U_{j_2}$ where $j_2\ge j_1$ is called $T{S}_{j_2}$. Note that we only remember the size of the larger item of the two, and recall that there is at most one such bin (out of all $k$ types for such a bin) at every time.

• $\mathrm{■}$

  A bin with items of sizes $U_{j_1}$ and $V_{j_2}$ where $j_2\ge j_1$ is called $S{L}_{j_2}$. Note that we only remember the size of the larger item of the two.

To summarize we recall the number of items in a bin as well as the size of its largest item.

We assume by contradiction that one of the stated pairs of bins exists, and show that none of the two orders of creation (by BF) for the two bins is possible. Since every pair of items can be packed into a bin together, the first bin of the two already has two items when the second one receives its first item. This excludes the option that an $S{L}_{j_1}$ bin receives its first item though an $O{S}_{j_2}$ bin exists for $j_2\le j_1$, and that a $T{S}_{j_1}$ bin receives its first item while an $O{L}_{j_2}$ bin exists for $j_2\ge j_1$. We are left with four cases where a new bin is opened when the other bin already has two items. Moreover, we use the property that no item is larger than $\frac{1}{2}$ while every item is larger than $\frac{1}{4}$, so the total size of two items is always larger than that of one item.

Consider an $S{L}_{j_1}$ bin and a $T{S}_{j_2}$ bin such that $j_2\le j_1$ that were created in this order. Neither the first item nor the second item of the $T{S}_{j_2}$ could be packed into the $S{L}_{j_1}$ bin (since two items are larger than one item, BF would have preferred the $S{L}_{j_1}$ bin). Since the $S{L}_{j_1}$ bin is not ready, it has an item of size $V_{j_1}$, and an item of size at most $U_{j_1}$. The $T{S}_{j_2}$ bin has an item at most $U_{j_2}\le U_{j_1}$ (in fact it has two such items). This contradicts the fact that no item of the $T{S}_{j_2}$ could be packed into the $S{L}_{j_1}$ bin. Similarly, consider the case of an $S{L}_{j_1}$ bin and an $O{S}_{j_2}$ bin such that $j_2\le j_1$, that were created in this order. A contradiction is reached in the same way (the second bin has just one item of size $U_{j_2}$ but this is sufficient for the contradiction.

Consider a $T{S}_{j_2}$ bin and an $S{L}_{j_1}$ bin that were created in this order. The smaller item of the $S{L}_{j_1}$ bin could have been packed into the $T{S}_{j_2}$ bin (no matter what the values $j_1,j_2$ are). Consider a $T{S}_{j_1}$ bin and an $O{L}_{j_2}$ bin such that $j_2\ge j_1$ that were created in this order. The total size of two items of size at most $U_{j_1}$ each and one item of size $V_{j_2}\le V_{j_1}$ can be packed together. $◀$

We have seen that there can be at most one $T{S}_i$ bin that is not ready (for some $i$). We extend this claim for $S{L}_{j_1}$ bins that are not ready (for some $j_1$).

Let $U_{j_2},U_{j_3}$ be the sizes of items packed with items of sizes $V_{j_1}$ into these bins. Since the bins are not ready, it holds that $j_1\ge j_2,j_3$. Assume that the item of size $U_{j_3}$ is packed into the bin that was created later by BF. Since $U_{j_2},U_{j_3}\le U_{j_1}$, the item of size $U_{j_3}$ could be packed into the first $S{L}_{j_1}$ bin, and BF would have packed it there. $◀$

Note that we did not exclude the option of a pair of bins that are an $S{L}_{j_1}$ bin and a $S{L}_{j_2}$ bin (for $j_1\ne j_2$) that are not ready, and this is in fact possible. For example, if an item of size $V_1$ was packed with an item of size $U_1$ and then an item of size $V_2$ arrives followed by an item of size $U_2$, BF will have one $S{L}_1$ bin and one $S{L}_2$ bin, none of which is ready.

To define a suitable Markov chain for the analysis of BF on our family of instances, we discuss its states and transition probabilities. Every state has a subset of bins that is not ready. The initial state has an empty set of such bins. Since there are $k$ options for $S{L}_i$ bins where each state may have at most one bin for every index, every state has a subset of indexes of $\{1,2,\mathrm{\dots },k\}$ of such bins. We discuss the set of states as a function of the larger index $i$ such that the state has an $S{L}_i$ bin (and also states without such bins for which we let $i=0$).

For a fixed value of $i$ and any set of values for ($2^{i-1}$ possible subsets of $S{L}_j$ bins for ) the following states exist (where the selected subset is called the specific subset), such that they are partitioned into seven types:

1. 1.

   In addition to the specific subset there are no other bins that are not ready.

2. 2.

   In addition to the specific subset there is an $OH$ bin and no other bins.

3. 3.

   In addition to the specific subset there is an $O{L}_{\mathrm{\ell }}$ bin and no other bins. Such a state exists for any $1\le \mathrm{\ell }\le k$.

4. 4.

   In addition to the specific subset there is an $O{S}_{\mathrm{\ell }}$ bin and no other bins. Such a state exists for any $i+1\le \mathrm{\ell }\le k$.

5. 5.

   In addition to the specific subset there is a $T{S}_{\mathrm{\ell }}$ bin and no other bins. Such a state exists for any $i+1\le \mathrm{\ell }\le k$.

6. 6.

   In addition to the specific subset and a $T{S}_{\mathrm{\ell }}$ for a fixed $\mathrm{\ell }$, there is also an $OH$ bin. Such a state exists for any $i+1\le \mathrm{\ell }\le k$.

7. 7.

   In addition to the specific subset and a $T{S}_{\mathrm{\ell }}$ for a fixed $\mathrm{\ell }$, there is also an $O{L}_q$ bin. Such a state exists for any $i+1\le \mathrm{\ell }\le k$ and $1\le q\le \mathrm{\ell }-1$.

This set of states includes all possible states based on the properties proved above. The next lemma enumerates the possible states.

Next, we explain the transitions for all states with a new item of each one of the sizes. The probability of the transition is equal to the probability of the item, as explained later. For an item of size $Z$, given a state which is a collection of bins that are not ready, there are two cases. If there is a bin with a single item, the new item is packed there, and the transition it to the state which has the same set of bins excluding the bin with the single item that became ready. Since there is at most one bin with a single item for each state, the transition is well-defined. If the state has no bin with a single item, the transition is to a state that contains the same collection of bins and also $OH$.

For an item of size $V_i$, the transition is as follows. If the collection of bins of the current state has a $T{S}_j$ bin such that $j\le i$, the transition is to a state with the same collection of bins excluding the $T{S}_j$ bin. Otherwise, if the collection of bins of the state has a bin with a single item, the new item is packed there and we find whether the bin becomes ready. If it is a $OH$ bin or a $O{L}_{\mathrm{\ell }}$ bin for some value of $\mathrm{\ell }$, it becomes ready. If the bin with a single item is $O{S}_{\mathrm{\ell }}$ it becomes ready if $\mathrm{\ell }>i$, and otherwise it becomes a $S{L}_i$ bin. Thus the transition is to a state that contains the same collection of bins excluding the bin that was used to pack the item. If this bin did not become ready, an $S{L}_i$ bin is added to the collection of the state. Note that in the case that the state has an additional bin there was no $S{L}_i$ bin in the state because in the case $\mathrm{\ell }\le i$ there cannot be an $O{S}_{\mathrm{\ell }}$ bin and an $S{L}_i$ bin with $i\ge \mathrm{\ell }$ at the same time by Lemma 7. If there is also no bin with a single item, an $O{L}_i$ bin is created, and the transition is to a state that contains the same collection of bins as the previous state, together with an $O{L}_i$ bin.

For an item of size $U_i$, the transition is as follows. If there is an $S{L}_j$ bin such that $i\le j$, the item is packed there and the bin becomes ready. Since there may be multiple such bins of the form $S{L}_j$ (with $i\le j$ and different values of $j$), the one with the smallest value of $j$ is chosen. In this case we show that this is indeed the selection of BF. For two bins that are $S{L}_{j_1}$ and $S{L}_{j_2}$ bins for $j_1>j_2$, it holds that the total size for the first bin is at most $V_{j_1}+U_{j_1}$ and the total size of the second bin is at least $V_{j_2}+U_1$. It holds that the difference is at least

since $j_1\ge j_2+1$ and $j_2\ge 1$, and similarly to previous calculations. If there is no $S{L}_j$ bin with $i\le j$, but there is an $T{S}_j$ bin, that bin is used and becomes ready. Otherwise, if there is a bin with a single item, the new item is packed there. The bin becomes ready if it is an $OH$ bin. If it is an $O{S}_j$ bin, it does not become ready and it turns into an $T{S}_p$ bin where $p=\max \{i,j\}$ (and there was no bin with two items of size below $\frac{1}{3}$ before this). If it is an $O{L}_j$ bin, it becomes ready if and otherwise it becomes an $S{L}_j$ bin (which did not exist because there was no $S{L}_j$ bin for $j\ge i$ if we reach this stage). If there was also no bin with a single item, a new $O{S}_i$ bin is created. The collection of bins of the state is modified as follows. If an existing bin was used for the item and the bin became ready, it is removed from the collection. If it did not become ready, the previous bin is removed from the collection and the new one is added instead. If the item is packed into a new bin, the new bin is added to the collection.

Using the set of states and the corresponding transitions, we construct the Markov chain, and define the system of equations corresponding to the equilibrium as a system of linear equations. We solved it for different sets of probabilities for input items using online tools. We used the property that a lower bound for a randomly created input can be used as a lower bound for randomly permuted inputs.

For inputs with $N$ items, we use probabilities $p_0$ for an item of size $Z$ and $p_1,p_2,\mathrm{\dots },p_k$ such that an item of size $U_i$ has probability of $p_i$ while an item of size $V_i$ has probability $p_{i+k}\le p_i/2$. Obviously we ensure that $p_0+{\sum }_{i=1}^{2k}{p}_i=1$. An optimal solution has cost that is very close to

This holds since for every $1\le i\le k$, if there are exactly $p_i\cdot N$ items of size $U_i$ and $p_{i+k}\cdot N$ items of size $V_i$, it is possible to pack the items in triples with at most one item of size $V_i$ in each triple (if $p_i>2p_{i+k}$ some triples have three items of size $U_i$).

The (expected) cost of the algorithm is the sum of probabilities of transitions from a state without a bin consisting of a single item to a state with such a bin multiplied by $N$. The calculation requires the equilibrium probabilities of states, and transition probabilities are calculated using the probabilities for different items.

We have compared the results of our program on multiple inputs to the outputs of the program of [29] and always obtain the same result (at least eight first digits after the decimal point). However, for our largest inputs (for $k=9$) we could only run our program.

In this way we get the lower bound $1.15539228$ using both programs (with a cost of approximately $0.40092127\cdot N$ for BF) using the probabilities

The improved bound for $k=9$ is a lower bound of $1.15582656$ (with a cost of approximately $0.398760164\cdot N$ for BF) using the probabilities (where for $1\le i\le 9$, we let $p_i=2\cdot p_{i+9}$):

We have thus proved the next theorem.

We use a direct proof, considering all permutations of a fixed set of items. Let $N>0$ be a large integer. The input consists of $N$ items of size $\frac{1}{N}$ each (larger items) and $N+1$ items of size $\frac{1}{N+1}$ each (smaller items). An optimal offline solution packs two completely full bins, such that one bin has all larger items and the other bin has all smaller items.

In order for a solution to use two bins rather than three bins, each bin has to contain items of total size exactly $1$. We claim that a bin that has at least one item of each size cannot have a total size of exactly $1$. Assume that a bin has $x\ge 1$ larger items and $y\ge 1$ smaller items, and it has a total size of $1$. We have $\frac{x}{N}+\frac{y}{N+1}=1$, and equivalently $(N+1)\cdot x+N\cdot y=N(N+1)$. Since the two variables $x,y$ are integral, we use simple number theory arguments. The numbers $N+1$ and $N$ are coprime. Since $(N+1)\cdot x=N(N+1-y)$, we find that $x$ is divisible by $N$. Since $N\cdot y=(N+1)(N-x)$, we conclude that $y$ is divisible by $N+1$. Thus, $x\ge N$ and $y\ge N+1$, and we get a total size of at least $2$, which is a contradiction since these items fit into one bin.

There are $(2N+1)!$ possible input permutations. We find those permutations that BF packs two bins for. If the first item of the permutation is larger, all larger items have to appear consecutively in the permutation such that the first bin will not contain a smaller item. If the first item of the permutation is smaller, the first bin has to receive at least $N$ smaller items that have to appear consecutively. This property guarantees that there is no space for a larger item (and one additional smaller item may appear later). The number of permutations where all larger items appear as the first $N$ items is $N!\cdot (N+1)!$, due to permuting the prefix of larger items and permuting the suffix of smaller items. The permutations where there are $N$ smaller items at the beginning differ not only by the order but also by the smaller item that appears in the suffix of length $N+1$. Thus, this number is $(N+1)\cdot N!\cdot (N+1)!$. In total, for $(N+1)(N+2)\cdot {(N!)}^2=(N+2)!\cdot N!$ permutations, the number of bins is $2$, while any other permutation results in (at least) three bins for BF.

We would like to show that the expected number of bins tends to $3$ as $N$ grows. Thus, we find an upper bound on $\frac{(N+2)!\cdot N!}{(2N+1)!}$:

since $\frac{i+1}{N+i+2}\le \frac{1}{2}$ for . The expected number of bins of BF for the given input is therefore at least $3-\frac{1}{2^{N-1}}$. $◀$