Misplaced Pages

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

${\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 , 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 , 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,B,...B, by the order they are opened. For each i in 1,...,k, we prove that the sum of B plus the bonus of B is at least 5/6: sum(B)+bonus(B) ≥ 5/6. Indeed, if sum(B) ≥ 5/6 then the inequality is trivial. Otherwise, let sum(B) := 1 - x. Note that x is between 1/6 and 2/6, since sum(B) is between 2/3 and 5/6. Since B is opened after B, B contains at least two items, say c1 and c2, that do not fit into B, that is: c1,c2 > 1-sum(B) = x > 1/6. Then the bonus of each of c1 and c2 is at least x/2 - 1/12. Therefore, the bonus of B is at least x-1/6, so sum(B) + bonus(B) ≥ (1-x)+(x-1/6) = 5/6.
• We can apply the above inequality to successive pairs, and get: sum(B) + bonus(B) + sum(B) + bonus(B) + ... + sum(B) + bonus(B) ≥ 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: (x3), (x7). All bin sums are 101.
• The First Fit packing contains 17 bins: , , (x5), (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.

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.

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):

• ${\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).

Approximation ratio

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}$.

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.

References

1. Ullman, J. D. (1971). "The performance of a memory allocation algorithm". Technical Report 100 Princeton Univ.
2. Garey, M. R; Graham, R. L; Ullman, J. D. (1972). "Worst-case analysis of memory allocation algorithms". Proceedings of the fourth annual ACM symposium on Theory of computing - STOC '72. pp. 143–150. doi:10.1145/800152.804907. S2CID 26654056.
3. David S. Johnson, Alan J. Demers, Jeffrey D. Ullman, M. R. Garey, Ronald L. Graham. Worst-Case Performance Bounds for Simple One-Dimensional Packing Algorithms. SICOMP, Volume 3, Issue 4. 1974.
4. Garey, M. R; Graham, R. L; Johnson, D. S; Yao, Andrew Chi-Chih (1976). "Resource constrained scheduling as generalized bin packing". Journal of Combinatorial Theory, Series A. 21 (3): 257–298. doi:10.1016/0097-3165(76)90001-7. ISSN 0097-3165.
5. Xia, Binzhou; Tan, Zhiyi (August 2010). "Tighter bounds of the First Fit algorithm for the bin-packing problem". Discrete Applied Mathematics. 158 (15): 1668–1675. doi:10.1016/j.dam.2010.05.026.
6. ^ Dósa, György; Sgall, Jiri (2013). "First Fit bin packing: A tight analysis". 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013). 20. Schloss Dagstuhl–Leibniz-Zentrum für Informatik: 538–549. doi:10.4230/LIPIcs.STACS.2013.538.
7. Garey, M. R.; Graham, R. L.; Ullman, J. D. (1972-05-01). "Worst-case analysis of memory allocation algorithms". Proceedings of the fourth annual ACM symposium on Theory of computing - STOC '72. New York, NY, USA: Association for Computing Machinery. pp. 143–150. doi:10.1145/800152.804907. ISBN 978-1-4503-7457-6. S2CID 26654056.
8. Johnson, D. S.; Demers, A.; Ullman, J. D.; Garey, M. R.; Graham, R. L. (December 1974). "Worst-Case Performance Bounds for Simple One-Dimensional Packing Algorithms". SIAM Journal on Computing. 3 (4): 299–325. doi:10.1137/0203025. ISSN 0097-5397.
9. Coffman, E. G; Garey, M. R; Johnson, D. S (1987-12-01). "Bin packing with divisible item sizes". Journal of Complexity. 3 (4): 406–428. doi:10.1016/0885-064X(87)90009-4. ISSN 0885-064X.
10. ^ Yao, Andrew Chi-Chih (April 1980). "New Algorithms for Bin Packing". Journal of the ACM. 27 (2): 207–227. doi:10.1145/322186.322187. S2CID 7903339.

• Bin packing