Editing Bin packing problem (section)

== Approximation algorithms for bin packing ==
To measure the performance of an approximation algorithm there are two approximation ratios considered in the literature. For a given list of items <math>L</math> the number <math>A(L)</math> denotes the number of bins used when algorithm <math>A</math> is applied to list <math>L</math>, while <math>\mathrm{OPT}(L)</math> denotes the optimum number for this list. The absolute worst-case performance ratio <math>R_A</math> for an algorithm <math>A</math> is defined as

: <math>R_A \equiv \inf\{r \geq 1 : A(L)/\mathrm{OPT}(L) \leq r \text{ for all lists } L\}.</math>

On the other hand, the asymptotic worst-case ratio <math>R_A^{\infty}</math> is defined as

: <math>R_A^\infty \equiv \inf\{ r \geq 1: \exists N >0,  A(L)/\mathrm{OPT}(L) \leq r \text{ for all lists } L \text{ with } \mathrm{OPT}(L) \geq N\}.</math>

Equivalently, <math>R_A^{\infty}</math> is the smallest number such that there exists some constant ''K,'' such that for all lists ''L:'''''<ref name=":0" />'''

: <math>A(L) \leq R^{\infty}_A \cdot \mathrm{OPT}(L) + K</math>.

Additionally, one can restrict the lists to those for which all items have a size of at most <math>\alpha</math>.  For such lists, the bounded size performance ratios are denoted as <math>R_A(\text{size}\leq \alpha)</math> and <math>R_A^\infty(\text{size}\leq \alpha)</math>.

Approximation algorithms for bin packing can be classified into two categories:

# Online heuristics, that consider the items in a given order and place them one by one inside the bins.  These heuristics are also applicable to the offline version of this problem.
# Offline heuristics, that modify the given list of items e.g. by sorting the items by size. These algorithms are no longer applicable to the online variant of this problem. However, they have an improved approximation guarantee while maintaining the advantage of their small time-complexity. A sub-category of offline heuristics is asymptotic approximation schemes. These algorithms have an approximation guarantee of the form <math>(1+\varepsilon)\mathrm{OPT}(L) + C</math> for some constant that may depend on <math>1/\varepsilon</math>. For an arbitrarily large <math>\mathrm{OPT}(L)</math> these algorithms get arbitrarily close to <math>\mathrm{OPT}(L)</math>. However, this comes at the cost of a (drastically) increased time complexity compared to the heuristical approaches.