|
Their algorithm uses [[separation oracle]] to the dual LP.
=== Approximation algorithms; ===
The general scheme of approximation algorithms is:
* Separate the items to "small" (smaller than ''eB'', for some fraction e in (0,1)) and "large" (at least ''eB'').
* Handle the large items first:
** Round the item sizes in some way, such that the number of different sizes is at most some constant ''S.''
** Write the integer LP for the rounded instance. Since the number of sizes is ''S'' and there are at most 1/''e'' items in each bin, the total number of configurations is at most ''S''<sup>1/''e''</sup>.
** Solve the integer LP.
* Allocate the small items greedily, e.g. with [[next-fit bin packing]]. If no new bins are created, then we are done. If new bins are created, this means that all bins (except maybe the last one) are full up to at least (1-''e'')''B''. Therefore, the number of bins is at most OPT/(1-''e'')+1 ≤ (1+2''e'')OPT+1.
The algorithms differ in how they round the instance and in how the solve the integer LP.
=== Rounding the large-items instance ===
Lueker and de-la-Vega and <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> invented the idea of ''adaptive input rounding''. Order the items by their size, and group them into 1/''e''<sup>2</sup> groups of cardinality ''ne''<sup>2</sup>. In each group, round the sizes upwards to the maximum size in the group. Now, there are only 1/''e''<sup>2</sup> different sizes. The solution of the rounded instance is feasible for the original instance too, but the number of bins may be larger than necessary. To quantify the loss, consider the instance rounded ''down'' to the maximum size in the ''previous'' group (the first group is rounded down to 0). The rounded-down instance ''D'' is almost equal to the rounded-up instance ''U'', except that in ''D'' there are some ''ne''<sup>2</sup> zeros while in ''U'' there are some ''ne''<sup>2</sup> large items instead; but their size is at most ''B''. Therefore, U requires at most ''ne''<sup>2</sup> more bins than ''D''. Since ''D'' requires fewer bins than the optimum, we get that Bins(''U'') ≤ OPT + ''ne''<sup>2</sup>, that is, we have an additive error that can be made as small as we like by choosing ''e''.
If all items are large (of size at least ''eB''), then each bin in OPT contains at most 1/''e'' items (of size at least ''eB''), so OPT must be at least ''en''. Therefore, Bins(''U'') ≤ (1+''e'')OPT.
Karmarkar and Karp<ref name=":12" /> present a more efficient rounding method which they call ''geometric rounding'' (in contrast to the linear rounding of de-la-Vega and Lueker). Based on these innovations, they present an algorithm with run-time polynomial in <math>n</math> and <math>1/\varepsilon</math>. Their algorithm finds a solution with size at most <math>\mathrm{OPT} + \mathcal{O}(\log^2(OPT))</math>.
=== Solving the integer LP for the rounded instance ===
A simple way to solve the integer LP is by exhaustive search. Since there are at most ''S<sup>1/e</sup>'' configurations, and for each configuration there are at most ''n'' possible values, there are at most <math> n^{S^{1/e}}</math> combinations to check. For each combination, we have to check ''S'' constraints, so the run-time is <math>S\cdot n^{S^{1/e}}</math>, which is polynomial in ''n'' when ''S, e'' are constant.<ref name=":2">{{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}}</ref>
=== Improvements ===
This technique was later improved by several authors:
* Rothvoss<ref name=":22">{{Cite journal|last=Rothvoß|first=T.|date=2013-10-01|title=Approximating Bin Packing within O(log OPT * Log Log OPT) Bins|url=https://ieeexplore.ieee.org/document/6686137|journal=2013 IEEE 54th Annual Symposium on Foundations of Computer Science|volume=|pages=20–29|arxiv=1301.4010|doi=10.1109/FOCS.2013.11|isbn=978-0-7695-5135-7|via=|s2cid=15905063}}</ref> presented an algorithm that generates a solution with size at most <math>\mathrm{OPT} + O(\log(\mathrm{OPT})\cdot \log\log(\mathrm{OPT}))</math>.
* Hoberg and Rothvoss<ref name=":3">{{Citation|last1=Hoberg|first1=Rebecca|title=A Logarithmic Additive Integrality Gap for Bin Packing|date=2017-01-01|url=https://epubs.siam.org/doi/abs/10.1137/1.9781611974782.172|work=Proceedings of the 2017 Annual ACM-SIAM Symposium on Discrete Algorithms|pages=2616–2625|series=Proceedings|publisher=Society for Industrial and Applied Mathematics|doi=10.1137/1.9781611974782.172|isbn=978-1-61197-478-2|access-date=2021-02-10|last2=Rothvoss|first2=Thomas|s2cid=1647463}}</ref> improved this algorithm to generate a solution with size at most <math>\mathrm{OPT} + O(\log(\mathrm{OPT}))</math>. The algorithm is randomized, and its running-time is polynomial in the total number of items.
== In machine scheduling ==
Consider the problem of [[unrelated-machines scheduling]]. In this problem, there are some ''m'' different machines that should process some ''n'' different jobs. When machine ''i'' processes job ''j'', it takes time ''p<sub>i</sub>''<sub>,''j''</sub>. The goal is to partition the jobs among the machines such that maximum completion time of a machine is as small as possible. The decision version of this problem is: given time ''T'', is there a partition in which the completion time of all machines is at most ''T''?
| 