Best-fit 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 best-fit algorithm uses the following heuristic:
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.
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 .[6] Furthermore, it holds that .
Since Worst-Fit is an AnyFit-algorithm, there exists an AnyFit-algorithm such that .[6]