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

The algorithm

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

* $A$-piece - size in $(1/2,1]$.
* $B_1$-piece - size in $(2/5,1/2]$.
* $B_2$-piece - size in $(1/3,2/5]$.
* $X$-piece - size in $(0,1/3]$.

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

Let $m \in \$ be a fixed integer. The next item $i \in L$ is assigned into a bin in -

* Class 1, if $i$ is an $A$-piece,
* Class 2, if $i$ is an $B_1$-piece,
* Class 3, if $i$ is an $B_2$-piece, but not the $(mk)$th $B_2$-piece seen so far, for any integer $k \geq 1$.
* Class 1, if $i$ is the $(mk)$th $B_2$-piece seen so far,
* Class 4, if $i$ is an $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 $RFF(L) \leq (5/3) \cdot \mathrm(L) +5$. There exists a family of lists $L_k$ with $RFF(L_k) = (5/3)\mathrm(L_k) +1/3$ for $\mathrm{OPT}(L) = 6k+1$.

See also

* First-fit-decreasing bin packing, 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: Th
prtpy package
contain
an implementation of first-fit

References

Bin packing