Content deleted Content added
Erel Segal (talk | contribs) |
Erel Segal (talk | contribs) No edit summary |
||
Line 1:
The '''Karmarkar-Karp (KK) bin packing algorithms''' are several related [[approximation algorithm]] for the [[bin packing problem]].<ref name=":12">{{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> The bin packing problem is a problem of packing items of different sizes into bins of identical capacity, such that the total number of bins is as small as possible. Finding the optimal solution is [[NP-hardness|computationally hard]]. [[Narendra Karmarkar|Karmarkar]] and [[Richard M. Karp|Karp]] devised an algorithm that runs in [[Polynomial-time|polynomial time]] and finds a solution with at most <math>\mathrm{OPT} + \mathcal{O}(\log^2(OPT))</math> bins, where OPT is the number of bins in the optimal solution. They also devised several other algorithms with slightly different approximation guarantees and run-time bounds.
The KK techniques were improved later, to provide even better approximations: an algorithm by Rothvoss<ref name=":2">{{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> uses at most <math>\mathrm{OPT} + O(\log(\mathrm{OPT})\cdot \log\log(\mathrm{OPT}))</math>bins, and an algorithm by 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> uses at most <math>\mathrm{OPT} + O(\log(\mathrm{OPT}))</math> bins. == Input ==
Line 22 ⟶ 24:
== Fractional bin packing ==
The main tool used by the KK algorithms is the fractional [[configuration linear program]]:<blockquote><math>\text{minimize}~~\mathbf{1}\cdot \mathbf{x}~~~\text{s.t.}~~ A \mathbf{x}\geq \mathbf{n}~~~\text{and}~~ \mathbf{x}\geq 0</math>.</blockquote>Here, '''''A''''' is a matrix with ''m'' rows. Each column of '''''A''''' represents a feasible ''configuration'' - a multiset of item-sizes, such that the sum of all these sizes is at most ''B''. The set of configurations is ''C''. '''x''' is a vector of size ''C.'' Each element ''x<sub>c</sub>'' of '''x''' represents the number of times configuration ''c'' is used. If '''x''' is integral then the solution to this problem is exactly OPT. Since '''x''' is allowed to be fractional, the solution might be smaller; denote it by LOPT. Moreover, let ''FOPT'' = (''a''<sub>1</sub>+...+''a<sub>n</sub>'')/''B'' = the theoretically-optimal number of bins, when all bins are completely filled with items or item fractions. The following relations are obvious:
*
* LOPT(I) ≤ OPT(I), since LOPT(I) is a solution to a minimization problem with fewer constraints.
* OPT(I) < 2*FOPT(I), since in any packing with at least 2*FOPT(I) bins, the sum of the two least-full bins is at most ''B'', so they can be combined into a single bin.
== References ==
| |||