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.
The first-fit algorithm uses the following heuristic: 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.
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.
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.
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.
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 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.
For claim 2, consider first an FF bin B with a single item.
Dósa and Sgall[6] present a tighter analysis that gets rid of the 3, and get that FF ≤ 17/10*OPT.
[7][8] The bin capacity is 101, and: 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.
[9]: Thm.3 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.
[10] 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.
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).