Best-fit bin packing

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 ${\displaystyle BF(L)\leq 1.7\mathrm {OPT} +3}$ was proven by Ullman[1] in 1971.
• An improved upper bound ${\displaystyle BF(L)\leq 1.7\mathrm {OPT} +2}$ was proved by Garey, Graham and Ullman,[2] Johnson and Demers.[3]
• Afterward, it was improved by Garey, Graham, Johnson, Ullman, Yao and Chi-Chih[4] to ${\displaystyle BF(L)\leq \lceil 1.7\mathrm {OPT} \rceil }$.
• Finally this bound was improved to ${\displaystyle FF(L)\leq \lfloor 1.7\mathrm {OPT} \rfloor }$ by Dósa and Sgall.[5] They also present an example input list ${\displaystyle L}$, for that ${\displaystyle BF(L)}$ matches this bound.

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 ${\displaystyle NF(L)=2\cdot \mathrm {OPT} (L)-2}$.[6] Furthermore, it holds that ${\displaystyle R_{WF}^{\infty }({\text{size}}\leq \alpha )=R_{NF}^{\infty }({\text{size}}\leq \alpha )}$.

Since Worst-Fit is an AnyFit-algorithm, there exists an AnyFit-algorithm such that ${\displaystyle R_{AF}^{\infty }(\alpha )=R_{NF}^{\infty }(\alpha )}$.[6]