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:
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.
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.sec.1.2 Define the "weight" of an input item as the item size "x" some "bonus" computed as follows:
formula_11
formula_12.
The asymptotic approximation ratio follows from two claims:
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:
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.
Consider now the FF bins "B" with two or more items.
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:
Performance with divisible item sizes.
An important special case of bin-packing is that which the item sizes form a "divisible sequence" (also called "factored"). A special case of divisible item sizes occurs in memory allocation in computer systems, where the item sizes are all powers of 2. If the item sizes are divisible, and in addition, the largest item sizes divides the bin size, then FF always finds an optimal packing.Thm.3
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):
Similarly, the bins are categorized into four classes: 1, 2, 3 and 4.
Let formula_21 be a fixed integer. The next item formula_22 is assigned into a bin in -
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 formula_37. There exists a family of lists formula_38 with formula_39 for formula_40.