Editing Bin packing problem (section)

== Online heuristics ==
In the [[Online algorithm|online]] version of the bin packing problem, the items arrive one after another and the (irreversible) decision where to place an item has to be made before knowing the next item or even if there will be another one. A diverse set of offline and online heuristics for bin-packing have been studied by [[David S. Johnson]] on his Ph.D. thesis.<ref name="johnson732">{{cite journal|last1=Johnson|first1=David S|date=1973|title=Near-optimal bin packing algorithms|url=https://dspace.mit.edu/bitstream/handle/1721.1/57819/17595570-MIT.pdf?sequence=2|journal=Massachusetts Institute of Technology}}</ref>

=== 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>.

=== Refined algorithms ===
Better approximation ratios are possible with heuristics that are not AnyFit. These heuristics usually keep several classes of open bins, devoted to items of different size ranges (see the linked pages for more information):

* '''[[Refined first-fit bin packing|Refined-first-fit bin packing]] (RFF)''' partitions the item sizes into four ranges: <math>\left(\frac 1 2,1\right]</math>, <math>\left(\frac 2 5, \frac 1 2\right]</math>, <math>\left(\frac 1 3, \frac 2 5\right]</math>, and <math>\left(0, \frac 1 3\right]</math>. Similarly, the bins are categorized into four classes. The next item <math>i \in L</math> is first assigned to its corresponding class. Inside that class, it is assigned to a bin using [[First-fit bin packing|first-fit]]. Note that this algorithm is not an Any-Fit algorithm since it may open a new bin despite the fact that the current item fits inside an open bin. This algorithm was first presented by Andrew Chi-Chih Yao,<ref name="Yao19802">{{cite journal|last1=Yao|first1=Andrew Chi-Chih|date=April 1980|title=New Algorithms for Bin Packing|journal=Journal of the ACM|volume=27|issue=2|pages=207–227|doi=10.1145/322186.322187|s2cid=7903339|doi-access=free}}</ref> who proved that it has an approximation guarantee of <math>RFF(L) \leq (5/3) \cdot \mathrm{OPT}(L) +5 </math> and presented a family of lists <math>L_k</math> with <math>RFF(L_k) = (5/3)\mathrm{OPT}(L_k) +1/3</math> for <math>\mathrm{OPT}(L) = 6k+1</math>.
* '''[[Harmonic bin packing|Harmonic-k]]''' partitions the interval of sizes <math>(0,1]</math> based on a [[Harmonic progression (mathematics)|Harmonic progression]] into <math>k-1</math> pieces <math>I_j := \left(\frac 1 {j+1}, \frac 1 j\right] </math> for <math>1\leq j < k</math> and <math>I_k := \left(0, \frac 1 k\right]</math> such that <math>\bigcup_{j=1}^k I_j = (0,1]</math>. This algorithm was first described by Lee and Lee.<ref name="LeeLee19852">{{cite journal|last1=Lee|first1=C. C.|last2=Lee|first2=D. T.|date=July 1985|title=A simple online bin-packing algorithm|journal=Journal of the ACM|volume=32|issue=3|pages=562–572|doi=10.1145/3828.3833|s2cid=15441740|doi-access=free}}</ref>  It has a time complexity of <math>\mathcal{O}(|L|\log(|L|))</math> and at each step, there are at most {{mvar|k}} open bins that can be potentially used to place items, i.e., it is a {{mvar|k}}-bounded space algorithm. For <math>k \rightarrow \infty</math>, its approximation ratio satisfies <math>R_{Hk}^{\infty} \approx 1.6910</math>, and it is asymptotically tight.
* '''[[Harmonic bin packing|Refined-harmonic]]''' combines ideas from Harmonic-k with ideas from [[Refined first-fit bin packing|Refined-First-Fit]]. It places the items larger than <math>\tfrac 1 3</math> similar as in Refined-First-Fit, while the smaller items are placed using Harmonic-k. The intuition for this strategy is to reduce the huge waste for bins containing pieces that are just larger than <math>\tfrac 1 2</math>. This algorithm was first described by Lee and Lee.<ref name="LeeLee19852" />  They proved that for <math>k = 20</math> it holds that <math>R^\infty_{RH} \leq 373/228</math>.

=== General lower bounds for online algorithms ===
Yao<ref name="Yao19802" /> proved in 1980 that there can be no online algorithm with an asymptotic competitive ratio smaller than <math>\tfrac 3 2</math>. Brown<ref>{{cite journal|last1=Donna J|first1=Brown|date=1979|title=A Lower Bound for On-Line One-Dimensional Bin Packing Algorithms.|url=https://apps.dtic.mil/dtic/tr/fulltext/u2/a085315.pdf|archive-url=https://web.archive.org/web/20220317212050/https://apps.dtic.mil/dtic/tr/fulltext/u2/a085315.pdf|url-status=live|archive-date=March 17, 2022|journal=Technical Rept.}}</ref> and Liang<ref>{{cite journal|last1=Liang|first1=Frank M.|date=1980|title=A lower bound for on-line bin packing|journal=Information Processing Letters|volume=10|issue=2|pages=76–79|doi=10.1016/S0020-0190(80)90077-0}}</ref> improved this bound to {{val|1.53635}}. Afterward, this bound was improved to {{val|1.54014}} by Vliet.<ref>{{cite journal|last1=van Vliet|first1=André|date=1992|title=An improved lower bound for on-line bin packing algorithms|journal=Information Processing Letters|volume=43|issue=5|pages=277–284|doi=10.1016/0020-0190(92)90223-I}}</ref>  In 2012, this lower bound was again improved by Békési and Galambos<ref>{{cite journal|last1=Balogh|first1=János|last2=Békési|first2=József|last3=Galambos|first3=Gábor|date=July 2012|title=New lower bounds for certain classes of bin packing algorithms|journal=Theoretical Computer Science|volume=440–441|pages=1–13|doi=10.1016/j.tcs.2012.04.017|doi-access=free}}</ref> to <math>\tfrac {248}{161} \approx 1.54037</math>.

=== Comparison table ===
{| class="wikitable"
!Algorithm
!Approximation guarantee
!Worst case list <math>L</math>
!Time-complexity
|-
|[[Next-fit bin packing|Next-fit (NF)]]
|<math>NF(L) \leq 2 \cdot \mathrm{OPT}(L) -1 </math><ref name="johnson732" />
|<math>NF(L) = 2 \cdot \mathrm{OPT}(L) -2 </math><ref name="johnson732" />
|<math>\mathcal{O}(|L|)</math>
|-
|[[First-fit bin packing|First-fit (FF)]]
|<math>FF(L) \leq \lfloor 1.7\mathrm{OPT}(L)\rfloor</math><ref name="DósaSgall2" />
|<math>FF(L) = \lfloor 1.7\mathrm{OPT}(L)\rfloor</math><ref name="DósaSgall2" />
|<math>\mathcal{O}(|L|\log(|L|))</math><ref name="johnson732" />
|-
|[[Best-fit bin packing|Best-fit (BF)]]
|<math>BF(L) \leq \lfloor 1.7\mathrm{OPT}(L) \rfloor </math><ref name="DósaSgall142" />
|<math>BF(L) =\lfloor 1.7\mathrm{OPT}(L) \rfloor </math><ref name="DósaSgall142" />
|<math>\mathcal{O}(|L|\log(|L|))</math><ref name="johnson732" />
|-
|Worst-Fit (WF)
|<math>WF(L) \leq 2 \cdot \mathrm{OPT}(L) -1 </math><ref name="johnson732" />
|<math>WF(L) = 2 \cdot \mathrm{OPT}(L) -2 </math><ref name="johnson732" />
|<math>\mathcal{O}(|L|\log(|L|))</math><ref name="johnson732" />
|-
|Almost-Worst-Fit (AWF)
|<math>R^{\infty}_{AWF} \leq 17/10</math><ref name="johnson732" />
|<math>R^{\infty}_{AWF} = 17/10</math><ref name="johnson732" />
|<math>\mathcal{O}(|L|\log(|L|))</math><ref name="johnson732" />
|-
|[[Refined first-fit bin packing|Refined-First-Fit]] (RFF)
|<math>RFF(L) \leq (5/3) \cdot \mathrm{OPT}(L) +5 </math><ref name="Yao19802" />
|<math>RFF(L)=(5/3)\mathrm{OPT}(L) +1/3</math> (for <math>\mathrm{OPT}(L) = 6k+1</math>)<ref name="Yao19802" />
|<math> \mathcal{O}(|L|\log(|L|))</math><ref name="Yao19802" />
|-
|[[Harmonic bin packing|Harmonic-k (Hk)]]
|<math>R_{Hk}^{\infty} \leq 1.69103</math> for <math>k \rightarrow \infty</math><ref name="LeeLee19852" />
|<math>R_{Hk}^{\infty} \geq 1.69103</math><ref name="LeeLee19852" />
|<math>\mathcal{O}(|L|\log(|L|)</math><ref name="LeeLee19852" />
|-
|[[Harmonic bin packing|Refined Harmonic]] (RH)
|<math>R_{RH}^{\infty} \leq 373/228 \approx 1.63597</math><ref name="LeeLee19852" />
|
|<math>\mathcal{O}(|L|)</math><ref name="LeeLee19852" />
|-
|Modified Harmonic (MH)
|<math>R_{MH}^{\infty} \leq 538/33 \approx 1.61562</math><ref name="RamananBLL19892">{{cite journal|last1=Ramanan|first1=Prakash|last2=Brown|first2=Donna J|last3=Lee|first3=C.C|last4=Lee|first4=D.T|date=September 1989|title=On-line bin packing in linear time|journal=Journal of Algorithms|volume=10|issue=3|pages=305–326|doi=10.1016/0196-6774(89)90031-X|hdl-access=free|hdl=2142/74206}}</ref>
|
|
|-
|Modified Harmonic 2 (MH2)
|<math>R_{MH2}^{\infty} \leq 239091/148304 \approx 1.61217</math><ref name="RamananBLL19892" />
|
|
|-
|Harmonic + 1 (H+1)
|
|<math>R_{H+1}^\infty \geq 1.59217</math><ref name="Seiden20022">{{cite journal|last1=Seiden|first1=Steven S.|date=2002|title=On the online bin packing problem|journal=Journal of the ACM|volume=49|issue=5|pages=640–671|doi=10.1145/585265.585269|s2cid=14164016}}</ref>
|
|-
|Harmonic ++ (H++)
|<math>R_{H++}^\infty \leq 1.58889</math><ref name="Seiden20022" />
|<math>R_{H++}^{\infty} \geq 1.58333</math><ref name="Seiden20022" />
|
|}