Editing Bin packing problem (section)

=== 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" />
|
|}