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, it 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^[1] in 1971.
• In 1972, this upper bound was improved to ${\displaystyle FF(L)\leq 1.7\mathrm {OPT} +2}$ by Garey, Graham and Ullman,^[2] Johnson and Demers.^[3]
• In 1976, it was improved by Garey, Graham, Johnson, Yao and Chi-Chih^[4] 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 ^[5] 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.^[6] They also present an example input list ${\displaystyle L}$, for which ${\displaystyle FF(L)}$ matches this bound.

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.^[7]

The algorithm[]

The items are categorized in four classes, according to their sizes:

• ${\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 items 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}$.^[7]

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.

References[]