Editing Bin packing problem (section)

== Offline algorithms ==
In the offline version of bin packing, the algorithm can see all the items before starting to place them into bins. This allows to attain improved approximation ratios.

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

=== Additive approximation ===
The [[Karmarkar-Karp bin packing algorithms|Karmarkar-Karp bin packing algorithm]] finds a solution with size at most <math>\mathrm{OPT} + \mathcal{O}(\log^2(\mathrm{OPT}))</math>, and runs in time polynomial in {{mvar |n}} (the polynomial has a high degree, at least 8).

Rothvoss<ref name=":2">{{Cite book |last=Rothvoß |first=T. |chapter=Approximating Bin Packing within O(log OPT · Log Log OPT) Bins |date=2013-10-01 |chapter-url=https://ieeexplore.ieee.org/document/6686137 |title=2013 IEEE 54th Annual Symposium on Foundations of Computer Science |pages=20–29 |arxiv=1301.4010 |doi=10.1109/FOCS.2013.11 |isbn=978-0-7695-5135-7 |s2cid=15905063}}</ref> presented an algorithm that generates a solution with at most <math>\mathrm{OPT} + \mathcal{O}(\log(\mathrm{OPT})\cdot \log\log(\mathrm{OPT}))</math> bins.

Hoberg and Rothvoss<ref name=":3">{{Citation |last1=Hoberg |first1=Rebecca |last2=Rothvoss |first2=Thomas |date=2017 |chapter=A Logarithmic Additive Integrality Gap for Bin Packing |title=Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms |publisher=SIAM |pages=2616–2625 |arxiv=1503.08796 |doi=10.1137/1.9781611974782.172 |isbn=978-1-61197-478-2 |doi-access=free |s2cid=1647463}}</ref> improved this algorithm to generate a solution with at most <math>\mathrm{OPT} + \mathcal{O}(\log(\mathrm{OPT}))</math> bins. The algorithm is randomized, and its running-time is polynomial in {{mvar |n}}.

=== Comparison table ===
{| class="wikitable"
!Algorithm
!Approximation guarantee
!Worst case instance
|-
|First-fit-decreasing (FFD)
|<math>\mathrm{FFD}(I) \leq \frac {11}9 \mathrm{OPT}(I) + \frac 6 9</math><ref name="Dosa072" />
|<math>\mathrm{FFD}(I) = \frac {11}9 \mathrm{OPT}(I) + \frac 6 9</math><ref name="Dosa072" />
|-
|Modified-first-fit-decreasing (MFFD)
|<math>\mathrm{MFFD}(I) \leq \frac {71}{60}\mathrm{OPT}(I) + 1</math><ref name="YueZhang19952" />
|<math>R_\mathrm{MFFD}^\infty \geq \frac {71}{60}</math><ref name="JohnsonGarey19852" />
|-
|Karmarkar and Karp
|<math>\mathrm{KK}(I) \leq \mathrm{OPT}(I) + O(\log^2{\mathrm{OPT}(I)})</math><ref name=":1">{{cite journal|last1=Karmarkar|first1=Narendra|last2=Karp|first2=Richard M.|date=November 1982|title=An efficient approximation scheme for the one-dimensional bin-packing problem|url=https://ieeexplore.ieee.org/document/4568405/references#references|journal=23rd Annual Symposium on Foundations of Computer Science (SFCS 1982)|pages=312–320|doi=10.1109/SFCS.1982.61|s2cid=18583908}}</ref>
|
|-
|Rothvoss
|<math>\mathrm{HB}(I) \leq \mathrm{OPT}(I) + O(\log{\mathrm{OPT}(I)}\log\log{\mathrm{OPT}(I)})</math><ref name=":2" />
|
|-
|Hoberg and Rothvoss
|<math>\mathrm{HB}(I) \leq \mathrm{OPT}(I) + O(\log{\mathrm{OPT}(I)})</math><ref name=":3" />
|
|}

=== Exact algorithms ===
Martello and Toth<ref>{{harvnb|Martello|Toth|1990|pp=237–240}}.</ref> developed an exact algorithm for the 1-dimensional bin-packing problem, called MTP. A faster alternative is the Bin Completion algorithm proposed by [[Richard E. Korf]] in 2002<ref>{{cite conference|last=Korf|first=Richard E.|author1-link=Richard E. Korf|year=2002|title=A new algorithm for optimal bin packing.|url=http://www.aaai.org/Papers/AAAI/2002/AAAI02-110.pdf|conference=AAAI-02}}</ref> and later improved.<ref name="Korf2003Korf2">[[Richard E. Korf]] (2003), ''[https://web.archive.org/web/20190823231238/https://pdfs.semanticscholar.org/616d/77a41020941a89e782e877bf4cf7bb5ec9a4.pdf An improved algorithm for optimal bin packing]''. Proceedings of the International Joint Conference on Artificial Intelligence, (pp. 1252–1258)</ref>

A further improvement was presented by Schreiber and Korf in 2013.<ref>{{citation|last1=Schreiber|first1=Ethan L.|title=Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence|pages=651–658|year=2013|series=IJCAI '13|chapter=Improved Bin Completion for Optimal Bin Packing and Number Partitioning|chapter-url=https://www.ijcai.org/Proceedings/13/Papers/103.pdf|location=Beijing, China|publisher=AAAI Press|isbn=978-1-57735-633-2|last2=Korf|first2=Richard E.|author2-link=Richard E. Korf}}</ref> The new Improved Bin Completion algorithm is shown to be up to five orders of magnitude faster than Bin Completion on non-trivial problems with 100 items, and outperforms the BCP (branch-and-cut-and-price) algorithm by Belov and Scheithauer on problems that have fewer than 20 bins as the optimal solution. Which algorithm performs best depends on problem properties like the number of items, the optimal number of bins, unused space in the optimal solution and value precision.

=== Small number of different sizes ===
A special case of bin packing is when there is a small number ''d'' of different item sizes. There can be many different items of each size. This case is also called ''[[high-multiplicity bin packing]]'', and It admits more efficient algorithms than the general problem.