Best-fit is an

online algorithm In computer science, an online algorithm is one that can process its input piece-by-piece in a serial fashion, i.e., in the order that the input is fed to the algorithm, without having the entire input available from the start. In contrast, an o ...

for

bin packing The bin packing problem is an optimization problem, in which items of different sizes must be packed into a finite number of bins or containers, each of a fixed given capacity, in a way that minimizes the number of bins used. The problem has m ...

. 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 best-fit algorithm uses the following

heuristic A heuristic (; ), or heuristic technique, is any approach to problem solving or self-discovery that employs a practical method that is not guaranteed to be optimal, perfect, or rational, but is nevertheless sufficient for reaching an immediat ...

: * It keeps a list of open bins, which is initially empty. * When an item arrives, it finds the bin with the ''maximum load'' 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 BF(L) the number of bins used by Best-Fit, and by OPT(L) the optimal number of bins possible for the list L. The analysis of BF(L) was done in several steps. * The first upper bound of

BF(L) \leq 1.7\mathrm+3

was proven by Ullman in 1971. * An improved upper bound

BF(L) \leq 1.7\mathrm+2

was proved by Garey, Graham and Ullman, Johnson and Demers.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. * Afterward, it was improved by Garey, Graham, Johnson, Ullman,Yao and Chi-Chih to

BF(L) \leq \lceil 1.7\mathrm\rceil

. * Finally 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 that

BF(L)

matches this bound.

Worst-fit

Worst-Fit is a "dual" algorithm to best-fit: it tries to put the next item in the bin with ''minimum'' load. This algorithm can behave as badly as Next-Fit, and will do so on the worst-case list for that

NF(L) = 2 \cdot \mathrm(L) -2

. Furthermore, it holds that

R_^(\text\leq \alpha) = R_^(\text\leq \alpha)

. Since Worst-Fit is an AnyFit-algorithm, there exists an AnyFit-algorithm such that

R_^(\alpha) = R_^{\infty}(\alpha)

References

Bin packing