First-fit bin packing

Here is a proof that the asymptotic ratio is at most 2. If there is an FF bin with sum less than 1/2, then the size of all remaining items is more than 1/2, so the sum of all following bins is more than 1/2. Therefore, all FF bins except at most one have sum at least 1/2. All optimal bins have sum at most 1, so the sum of all sizes is at most OPT. Therefore, number of FF bins is at most 1+OPT/(1/2) = 2*OPT+1

Consider first a special case in which all item sizes are at most 1/2. If there is an FF bin with sum less than 2/3, then the size of all remaining items is more than 1/3. Since the sizes are at most 1/2, all following bins (except maybe the last one) have at least two items, and sum larger than 2/3. Therefore, all FF bins except at most one have sum at least 2/3, and the number of FF bins is at most 2+OPT/(2/3) = 3/2*OPT+1.

The "problematic" items are those with size larger than 1/2. So, to improve the analysis, let's give every item larger than 1/2 a bonus of R. Define the weight of an item as its size plus its bonus. Define the weight of a set of items as the sum of weights of its contents.

Now, the weight of each FF bin with one item (except at most one) is at least 1/2+R, and the weight of each FF bin with two or more items (except at most one) is 2/3. Taking R=1/6 yields that the weight of all FF bins is at least 2/3.

On the other hand, the weight of every bin in the optimal packing is at most 1+R = 7/6, since each such bin has at most one item larger than 1/2. Therefore, the total weight of all items is at most 7/6*OPT, and the number of FF bins is at most 2+(7/6*OPT/(2/3)) = 7/4*OPT+2.

The following proof is adapted from.[6]^: sec.1.2 Define the weight of an input item as the item size x some bonus computed as follows:

${\displaystyle bonus(x):={\begin{cases}0&x\leq 1/6\\x/2-1/12&1/6<x<1/3\\1/12&1/3\leq x\leq 1/2\\1/3&1/2<x\end{cases}}}$

${\displaystyle weight(x):=x+bonus(x)}$.

The asymptotic approximation ratio follows from two claims:

1. In the optimal packing, the weight of each bin is at most 17/12;
2. In the First-Fit packing, the average weight of each bin is at least 5/6 = 10/12.

Therefore, asymptotically, the number of bins in the FF packing must be at most 17/10 * OPT.

For claim 1, it is sufficient to prove that, for any set B with sum at most 1, bonus(B) is at most 5/12. Indeed:

• If B has no item larger than 1/2, then it has at most five items larger than 1/6, and the bonus of each of them is at most 1/12;
• If B has an item larger than 1/2 but no item in [1/3,1/2], then it has room for at most two items in (1/6,1/3), and the sum of their bonuses is at most (1/2 / 2 - 1/6) = 1/12, so the total bonus is 4/12+1/12=5/12.
• If B has an item larger than 1/2 and an item in [1/3,1/2], then it has no more room for items of size larger than 1/6, so the total bonus is again 4/12+1/12 = 5/12.

Therefore, the weight of B is at most 1+5/12 = 17/12.

For claim 2, consider first an FF bin B with a single item.

• If sum(B)<1/2, then - by the way FF works - all items processed after B must be larger than 1/2 (otherwise they would have been inserted into B). Therefore, there is at most one FF bin with sum<1/2.
• Consider now all other bins B with a single item with sum(B)>1/2. For all these bins, weight(B)>1/2+1/3 = 5/6.

Consider now the FF bins B with two or more items.

• If sum(B)<2/3, then - by the way FF works - all items processed after B must be larger than 1/3 (otherwise they would have been inserted into B). Therefore, all following bins with two or more items are larger than 2/3. So there is at most one FF bin with two or more items and sum<2/3.
• Consider now all other bins with two or more items and sum>2/3. Denote them by B[1],B[2],...B[k], by the order they are opened. For each i in 1,...,k, we prove that the sum of B[i] plus the bonus of B[i+1] is at least 5/6: sum(B[i])+bonus(B[i+1]) >=5/6. Indeed, if sum(B[i]) >= 5/6 then the inequality is trivial. Otherwise, let sum(B[i]) := 1 - x. Note that x is between 1/6 and 2/6, since sum(B[i]) is between 2/3 and 5/6. Since B[i+1] is opened after B[i], B[i+1] contains at least two items, say c1 and c2, that do not fit into B[i], that is: c1,c2 > 1-sum(B[i]) = x > 1/6. Then the bonus of each of c1 and c2 is at least x/2 - 1/12. Therefore, the bonus of B[i+1] is at least x-1/6, so sum(B[i]) + bonus(B[i+1]) >= (1-x)+(x-1/6) = 5/6.
• We can apply the above inequality to successive pairs, and get: sum(B[1]) + bonus(B[2]) + sum(B[2]) + bonus(B[3]) + ... + sum(B[k-1]) + bonus(B[k]) >= 5/6*(k-1).

Therefore, the total weight of all FF bins is at least 5/6*(FF - 3) (where we subtract 3 for the single one-item bin with sum<1/2, single two-item bin with sum<2/3, and the k-1 from the two-item bins with sum>=2/3).

All in all, we get that 17/12*OPT >= 5/6*(FF-3), so FF <= 17/10*OPT+3.

Dósa and Sgall[6] present a tighter analysis that gets rid of the 3, and get that FF <= 17/10*OPT.

There are instances on which the performance bound of 1.7OPT is tight. The following example is based on.[7][8] The bin capacity is 101, and:

• The sequence is: 6 (x7), 10 (x7), 16 (x3), 34 (x10), 51 (x10).
• The optimal packing contains 10 bins: [51+34+16] (x3), [51+34+10+6] (x7). All bin sums are 101.
• The First Fit packing contains 17 bins: [6 (x7) + 10 (x5)], [10 (x2) + 16 (x3)], [34+34] (x5), [51] (x10).
  • The bin sums are: 92, 68, 68 (x5), 51 (x10).
  • The rewards (normalized to 101) are 0, 0, 16.8 (x5), 33.7 (x10).
  • The total weights (normalized to 101) are 92, 68, 84.8 (x5), 84.7 (x10). It can be seen that almost all weights are close to 101*5/6=84.1.

The items are categorized in four classes, according to their sizes (where the bin capacity is 1):

• ${\displaystyle A}$-piece - size in ${\displaystyle (1/2,1]}$.
• ${\displaystyle B_{1}}$-piece - size in ${\displaystyle (2/5,1/2]}$.
• ${\displaystyle B_{2}}$-piece - size in ${\displaystyle (1/3,2/5]}$.
• ${\displaystyle X}$-piece - size in ${\displaystyle (0,1/3]}$.

Similarly, the bins are categorized into four classes: 1, 2, 3 and 4.

Let ${\displaystyle m\in \{6,7,8,9\}}$ be a fixed integer. The next item ${\displaystyle i\in L}$ is assigned into a bin in -

• Class 1, if ${\displaystyle i}$ is an ${\displaystyle A}$-piece,
• Class 2, if ${\displaystyle i}$ is an ${\displaystyle B_{1}}$-piece,
• Class 3, if ${\displaystyle i}$ is an ${\displaystyle B_{2}}$-piece, but not the ${\displaystyle (mk)}$th ${\displaystyle B_{2}}$-piece seen so far, for any integer ${\displaystyle k\geq 1}$.
• Class 1, if ${\displaystyle i}$ is the ${\displaystyle (mk)}$th ${\displaystyle B_{2}}$-piece seen so far,
• Class 4, if ${\displaystyle i}$ is an ${\displaystyle X}$-piece.

Once the class of the item is selected, it is placed inside bins of that class using first-fit bin packing.

Note that RFF is not an Any-Fit algorithm since it may open a new bin despite the fact that the current item fits inside an open bin (from another class).

RFF has an approximation guarantee of ${\displaystyle RFF(L)\leq (5/3)\cdot \mathrm {OPT} (L)+5}$. There exists a family of lists ${\displaystyle L_{k}}$ with ${\displaystyle RFF(L_{k})=(5/3)\mathrm {OPT} (L_{k})+1/3}$ for ${\displaystyle \mathrm {OPT} (L)=6k+1}$.[9]