Editing Bin packing problem (section)

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