Abstrakt
In the bin packing problem we are given an instance consisting of a sequence of items with sizes between $0$ and $1$. The objective is to pack these items into the smallest possible number of bins of unit size. {\sc FirstFit} and {\sc BestFit} algorithms are simple online algorithms introduced in early seventies, when it was also shown that their asymptotic approximation ratio is equal to $1.7$.
We present a simple proof of this bound and survey recent developments that lead to the proof that also the absolute approximation ratio of these algorithms is exactly $1.7$. More precisely, if the optimum needs $\OPT$ bins, the algorithms use at most $\lfloor1.7\cdot\mbox{\sc OPT}\rfloor$ bins and for each value of $\OPT$, there are instances that actually need so many bins.
We also discuss bounded-space bin packing, where the online algorithm is allowed to keep only a fixed number of bins open for future items. In this model, a variant of {\sc BestFit} also has asymptotic approximation ratio $1.7$, although it is possible that the bound is significantly smaller if also the offline solution is required to satisfy the bounded-space restriction.