Editing Bin packing problem (section)

=== Single-class algorithms ===
There are many simple algorithms that use the following general scheme:
* For each item in the input list:
*# If the item fits into one of the currently open bins, then put it in one of these bins;
*# Otherwise, open a new bin and put the new item in it.

The algorithms differ in the criterion by which they choose the open bin for the new item in step 1 (see the linked pages for more information):

* [[Next-fit bin packing|'''Next Fit''']] '''(NF)''' always keeps a single open bin. When the new item does not fit into it, it closes the current bin and opens a new bin. Its advantage is that it is a bounded-space algorithm since it only needs to keep a single open bin in memory. Its disadvantage is that its asymptotic approximation ratio is 2. In particular, <math>NF(L) \leq 2 \cdot \mathrm{OPT}(L) -1 </math>, and for each <math>N \in \mathbb{N}</math> there exists a list {{mvar|L}} such that <math>\mathrm{OPT}(L) = N</math> and <math>NF(L) = 2 \cdot \mathrm{OPT}(L) -2</math>.<ref name="johnson732" /> Its asymptotic approximation ratio can be somewhat improved based on the item sizes: <math>R_{NF}^\infty(\text{size}\leq\alpha) \leq 2</math> for all <math>\alpha \geq 1/2</math> and <math>R_{NF}^\infty(\text{size}\leq\alpha) \leq 1/(1-\alpha)</math> for all <math>\alpha \leq 1/2</math>. For each algorithm {{mvar|A}} that is an AnyFit-algorithm it holds that <math>R_{A}^{\infty}(\text{size}\leq\alpha)\leq R_{NF}^{\infty}(\text{size}\leq\alpha)</math>.
* '''[[Next-fit bin packing|Next-k-Fit]]''' '''(NkF)''' is a variant of Next-Fit, but instead of keeping only one bin open, the algorithm keeps the last {{mvar|k}} bins open and chooses the first bin in which the item fits. Therefore, it is called a ''k-bounded space'' algorithm.<ref>{{cite book|last1=Gonzalez|first1=Teofilo F.|title=Handbook of approximation algorithms and metaheuristics. Volume 2 Contemporary and emerging applications|date=23 May 2018|publisher=Taylor & Francis Incorporated |isbn=9781498770156}}</ref> For <math>k\geq 2</math> the NkF delivers results that are improved compared to the results of NF, however, increasing {{mvar|k}} to constant values larger than {{mvar|2}} improves the algorithm no further in its worst-case behavior.  If algorithm {{mvar|A}} is an AlmostAnyFit-algorithm and <math>m = \lfloor 1/\alpha\rfloor \geq 2</math> then <math>R_{A}^{\infty}(\text{size}\leq\alpha)\leq R_{N2F}^{\infty}(\text{size}\leq\alpha) = 1+1/m</math>.<ref name="johnson732" />
* '''[[First-fit bin packing|First-Fit]] (FF)''' keeps all bins open, in the order in which they were opened. It attempts to place each new item into the ''first'' bin in which it fits. Its approximation ratio is <math>FF(L) \leq \lfloor 1.7\mathrm{OPT}\rfloor</math>, and there is a family of input lists {{mvar|L}} for which <math>FF(L)</math> matches this bound.<ref name="DósaSgall2">{{cite journal|last1=Dósa|first1=György|last2=Sgall|first2=Jiri|date=2013|title=First Fit bin packing: A tight analysis|url=http://drops.dagstuhl.de/opus/volltexte/2013/3963|journal=30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)|publisher=Schloss Dagstuhl–Leibniz-Zentrum für Informatik|volume=20|pages=538–549|doi=10.4230/LIPIcs.STACS.2013.538|doi-access=free }}</ref>
* [[Best-fit bin packing|'''Best-Fit''']] '''(BF)''', too, keeps all bins open, but attempts to place each new item into the bin with the ''maximum'' load in which it fits. Its approximation ratio is identical to that of FF, that is: <math>BF(L) \leq \lfloor 1.7\mathrm{OPT}\rfloor</math>, and there is a family of input lists {{mvar|L}} for which <math>BF(L)</math> matches this bound.<ref name="DósaSgall142">{{cite book|last1=György|first1=Dósa|last2=Sgall|first2=Jirí|title=Automata, Languages, and Programming |chapter=Optimal Analysis of Best Fit Bin Packing |date=2014|series=Lecture Notes in Computer Science|volume=8572|pages=429–441|doi=10.1007/978-3-662-43948-7_36|isbn=978-3-662-43947-0}}</ref>
*'''Worst-Fit (WF)''' attempts to place each new item into the bin with the ''minimum'' load. It can behave as badly as Next-Fit, and will do so on the worst-case list for that <math>NF(L) = 2 \cdot \mathrm{OPT}(L) -2 </math>. Furthermore, it holds that <math>R_{WF}^{\infty}(\text{size}\leq \alpha) = R_{NF}^{\infty}(\text{size}\leq \alpha)</math>. Since WF is an AnyFit-algorithm, there exists an AnyFit-algorithm such that <math>R_{AF}^{\infty}(\alpha) = R_{NF}^{\infty}(\alpha)</math>.<ref name="johnson732" />
* '''Almost Worst-Fit (AWF)''' attempts to place each new item inside the ''second most empty'' open bin (or emptiest bin if there are two such bins). If it does not fit, it tries the most empty one. It has an asymptotic worst-case ratio of <math>\tfrac {17}{10}</math>.<ref name="johnson732" />
In order to generalize these results, Johnson introduced two classes of online heuristics called ''any-fit algorithm'' and ''almost-any-fit'' algorithm:'''<ref name=":0" />'''{{Rp|470}}
* In an '''AnyFit (AF)''' algorithm, if the current nonempty bins are ''B''<sub>1</sub>,...,''B<sub>j</sub>'', then the current item will not be packed into ''B''<sub>''j''+1</sub> unless it does not fit in any of ''B''<sub>1</sub>,...,''B<sub>j</sub>''. The FF, WF, BF and AWF algorithms satisfy this condition. Johnson proved that, for any AnyFit algorithm A and any <math>\alpha</math>:
*:<math>R_{FF}^{\infty}(\alpha) \leq R_{A}^{\infty}(\alpha) \leq R_{WF}^{\infty}(\alpha)</math>.
* In an '''AlmostAnyFit (AAF)''' algorithm, if the current nonempty bins are ''B''<sub>1</sub>,...,''B<sub>j</sub>'', and of these bins, ''B<sub>k</sub>'' is the unique bin with the smallest load, then the current item will not be packed into ''B<sub>k</sub>'', unless it does not fit into any of the bins to its left. The FF, BF and AWF algorithms satisfy this condition, but WF does not. Johnson proved that, for any AAF algorithm A and any {{mvar|&alpha;}}:
*:<math>R_{A}^{\infty}(\alpha) = R_{FF}^{\infty}(\alpha) </math>  In particular: <math>R_{A}^{\infty} = 1.7 </math>.