Editing Bin packing problem (section)

=== Multiplicative approximation ===
The simplest technique used by offline approximation schemes is the following:

* Ordering the input list by descending size;
* Run an online algorithm on the ordered list.

Johnson<ref name="johnson732" /> proved that any AnyFit scheme A that runs on a list ordered by descending size has an asymptotic approximation ratio of<blockquote><math>1.22 \approx \frac{11}{9} \leq R^{\infty}_A \leq \frac{5}{4} = 1.25</math>.</blockquote>Some methods in this family are (see the linked pages for more information):

* '''[[First-fit-decreasing bin packing|First-fit-decreasing]] (FFD)''' orders the items by descending size, then calls First-Fit. Its approximation ratio is <math>FFD(I) = \frac{11}9 \mathrm{OPT}(I) + \frac 6 9</math>, and this is tight.<ref name="Dosa072">{{cite journal|last1=Dósa|first1=György|date=2007|title=The Tight Bound of First Fit Decreasing Bin-Packing Algorithm Is FFD(I) ≤ 11/9\mathrm{OPT}(I) + 6/9|journal=Combinatorics, Algorithms, Probabilistic and Experimental Methodologies. ESCAPE|doi=10.1007/978-3-540-74450-4_1}}</ref>
* '''[[Next-fit-decreasing]] (NFD)''' orders the items by descending size, then calls [[Next-fit bin packing|Next-Fit]].  Its approximate ratio is slightly less than 1.7 in the worst case.<ref>{{Cite journal|last1=Baker|first1=B. S.|last2=Coffman|first2=Jr., E. G.|date=1981-06-01|title=A Tight Asymptotic Bound for Next-Fit-Decreasing Bin-Packing|url=https://epubs.siam.org/doi/abs/10.1137/0602019|journal=SIAM Journal on Algebraic and Discrete Methods|volume=2|issue=2|pages=147–152|doi=10.1137/0602019|issn=0196-5212}}</ref> It has also been analyzed probabilistically.<ref>{{Cite journal|last1=Csirik|first1=J.|last2=Galambos|first2=G.|last3=Frenk|first3=J.B.G.|last4=Frieze|first4=A.M.|last5=Rinnooy Kan|first5=A.H.G.|date=1986-11-01|title=A probabilistic analysis of the next fit decreasing bin packing heuristic|url=https://www.sciencedirect.com/science/article/abs/pii/0167637786900131|journal=Operations Research Letters|language=en|volume=5|issue=5|pages=233–236|doi=10.1016/0167-6377(86)90013-1|issn=0167-6377|hdl=1765/11645|s2cid=50663185 |hdl-access=free}}</ref> Next-Fit packs a list and its inverse into the same number of bins. Therefore, Next-Fit-Increasing has the same performance as Next-Fit-Decreasing.<ref>{{Cite journal|last1=Fisher|first1=David C.|date=1988-12-01|title=Next-fit packs a list and its reverse into the same number of bins|url=https://www.sciencedirect.com/science/article/abs/pii/0167637788900600|journal=Operations Research Letters|language=en|volume=7|issue=6|pages=291–293|doi=10.1016/0167-6377(88)90060-0|issn=0167-6377}}</ref>
* '''[[Modified first-fit-decreasing]] (MFFD)<ref name="JohnsonGarey19852">{{cite journal|last1=Johnson|first1=David S|last2=Garey|first2=Michael R|date=October 1985|title=A 7160 theorem for bin packing|journal=Journal of Complexity|volume=1|issue=1|pages=65–106|doi=10.1016/0885-064X(85)90022-6|doi-access=free}}</ref>''', improves on FFD for items larger than half a bin by classifying items by size into four size classes large, medium, small, and tiny, corresponding to items with size > 1/2 bin, > 1/3 bin, > 1/6 bin, and smaller items respectively.  Its approximation guarantee is <math>MFFD(I) \leq \frac {71}{60}\mathrm{OPT}(I) + 1</math>.<ref name="YueZhang19952">{{cite journal|last1=Yue|first1=Minyi|last2=Zhang|first2=Lei|date=July 1995|title=A simple proof of the inequality MFFD(L) ≤ 71/60 OPT(L) + 1,L for the MFFD bin-packing algorithm|journal=Acta Mathematicae Applicatae Sinica|volume=11|issue=3|pages=318–330|doi=10.1007/BF02011198|s2cid=118263129}}</ref>
Fernandez de la Vega and Lueker<ref>{{cite journal|last1=Fernandez de la Vega|first1=W.|last2=Lueker|first2=G. S.|date=1981|title=Bin packing can be solved within 1 + ε in linear time|journal=Combinatorica|language=en|volume=1|issue=4|pages=349–355|doi=10.1007/BF02579456|issn=1439-6912|s2cid=10519631}}</ref> presented a [[Polynomial-time approximation scheme|PTAS]] for bin packing. For every <math>\varepsilon>0</math>, their algorithm finds a solution with size at most <math>(1+\varepsilon)\mathrm{OPT} + 1</math> and runs in time  <math>\mathcal{O}(n\log(1/\varepsilon)) + \mathcal{O}_{\varepsilon}(1)</math>, where <math>\mathcal{O}_{\varepsilon}(1)</math> denotes a function only dependent on <math>1/\varepsilon</math>. For this algorithm, they invented the method of ''adaptive input rounding'': the input numbers are grouped and rounded up to the value of the maximum in each group. This yields an instance with a small number of different sizes, which can be solved exactly using the [[configuration linear program]].<ref>{{Cite web|last=Claire Mathieu|title=Approximation Algorithms Part I, Week 3: bin packing|url=https://www.coursera.org/learn/approximation-algorithms-part-1/home/week/3|url-status=live|website=Coursera|archive-url=https://web.archive.org/web/20210715093252/https://www.coursera.org/learn/approximation-algorithms-part-1/home/week/3 |archive-date=2021-07-15 }}</ref>