First-fit bin packing

First-fit (FF) is an online algorithm for bin packing. Its input is a list of items of different sizes. Its output is a packing - a partition of the items into bins of fixed capacity, such that the sum of sizes of items in each bin is at most the capacity. Ideally, we would like to use as few bins as possible, but minimizing the number of bins is an NP-hard problem. The first-fit algorithm uses the following heuristic:

• It keeps a list of open bins, which is initially empty.
• When an item arrives, find the first bin into which the item can fit, if any.
  • If such a bin is found, the new item is placed inside it.
  • Otherwise, a new bin is opened and the coming item is placed inside it.

Approximation ratio

Denote by FF(L) the number of bins used by First-Fit, and by OPT(L) the optimal number of bins possible for the list L. The analysis of FF(L) was done in several steps.

• The first upper bound of [math]\displaystyle{ FF(L) \leq 1.7\mathrm{OPT}+3 }[/math] for FF was proven by Ullman in 1971.
• In 1972, this upper bound was improved to [math]\displaystyle{ FF(L) \leq 1.7\mathrm{OPT}+2 }[/math] by Garey, Graham and Ullman, Johnson and Demers.
• In 1976, it was improved by Garey, Graham, Johnson, Yao and Chi-Chih to [math]\displaystyle{ FF(L) \leq \lceil 1.7\mathrm{OPT}\rceil }[/math], which is equivalent to [math]\displaystyle{ FF(L) \leq 1.7\mathrm{OPT}+0.9 }[/math] due to the integrality of [math]\displaystyle{ FF(L) }[/math] and [math]\displaystyle{ \mathrm{OPT} }[/math].
• The next improvement, by Xia and Tan in 2010, lowered the bound to [math]\displaystyle{ FF(L) \leq 1.7\mathrm{OPT}+0.7 }[/math].
• Finally, in 2013, this bound was improved to [math]\displaystyle{ FF(L) \leq \lfloor 1.7\mathrm{OPT}\rfloor }[/math] by Dósa and Sgall. They also present an example input list [math]\displaystyle{ L }[/math], for which [math]\displaystyle{ FF(L) }[/math] matches this bound.

Below we explain the proof idea.

Asymptotic ratio at most 2

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

Asymptotic ratio at most 1.75

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.

Asymptotic ratio at most 1.7

The following proof is adapted from. Define the weight of an input item as the item size x some bonus computed as follows:

[math]\displaystyle{ bonus(x) := \begin{cases} 0 & x \leq 1/6 \\ x/2-1/12 & 1/6\lt x\lt 1/3 \\ 1/12 & 1/3 \leq x \leq 1/2 \\ 1/3 & 1/2 \lt x \end{cases} }[/math]

[math]\displaystyle{ weight(x) := x + bonus(x) }[/math].

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 present a tighter analysis that gets rid of the 3, and get that FF <= 17/10*OPT.

Lower bound

There are instances on which the performance bound of 1.7OPT is tight. The following example is based on. 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.

Refined first-fit

Refined-First-Fit (RFF) is another online algorithm for bin packing, that improves on the previously developed FF algorithm. It was presented by Andrew Chi-Chih Yao.

The algorithm

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

• [math]\displaystyle{ A }[/math]-piece - size in [math]\displaystyle{ (1/2,1] }[/math].
• [math]\displaystyle{ B_1 }[/math]-piece - size in [math]\displaystyle{ (2/5,1/2] }[/math].
• [math]\displaystyle{ B_2 }[/math]-piece - size in [math]\displaystyle{ (1/3,2/5] }[/math].
• [math]\displaystyle{ X }[/math]-piece - size in [math]\displaystyle{ (0,1/3] }[/math].

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

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

• Class 1, if [math]\displaystyle{ i }[/math] is an [math]\displaystyle{ A }[/math]-piece,
• Class 2, if [math]\displaystyle{ i }[/math] is an [math]\displaystyle{ B_1 }[/math]-piece,
• Class 3, if [math]\displaystyle{ i }[/math] is an [math]\displaystyle{ B_2 }[/math]-piece, but not the [math]\displaystyle{ (mk) }[/math]th [math]\displaystyle{ B_2 }[/math]-piece seen so far, for any integer [math]\displaystyle{ k \geq 1 }[/math].
• Class 1, if [math]\displaystyle{ i }[/math] is the [math]\displaystyle{ (mk) }[/math]th [math]\displaystyle{ B_2 }[/math]-piece seen so far,
• Class 4, if [math]\displaystyle{ i }[/math] is an [math]\displaystyle{ X }[/math]-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).

Approximation ratio

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

See also

• First-Fit-Decreasing (FFD) is the offline variant of First-Fit: it accepts all input items, orders them by descending size, and calls First-Fit. Its asymptotic approximation ratio is much better: about 1.222 instead of 1.7.

Implementations

• Python: The prtpy package contains an implementation of first-fit.