Content deleted Content added
Erel Segal (talk | contribs) ←Created page with 'The '''Karmarkar-Karp bin packing algorithm''' is an 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...' |
Erel Segal (talk | contribs) No edit summary |
||
Line 4:
Their 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 ==
The input to a bin-packing problem is a set of items of different sizes, ''a''<sub>1</sub>,...''a<sub>n</sub>''. The following notation is used:
* ''n'' - the number of items.
* ''m'' - the number of different item sizes.
* ''B'' - the bin size.
* ''e'' - a fraction in (0,1), such that ''eB'' is the smallest size of an item.
* ''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.
== Guarantees ==
Karmarkar and Karp actually present four different algorithms. Their run-time depends on a function <math>T(\cdot,\cdot)</math>, which is a polynomial function describing the time it takes to solve the [[configuration linear program]]: <math>T(m,n)\in O(m^8\log{m}\log^2{n} + m^4 n \log{m}\log{n} )</math>. The algorithms attain the following guarantees:
* At most <math>\mathrm{OPT} + \mathcal{O}(\log^2 OPT)</math> bins, with run-time in <math>O(T(FOPT,n))</math>.
* At most <math>\mathrm{OPT} + \mathcal{O}(\log^2 m)</math> bins, with run-time in <math>O(T(m,n))</math>.
* At most <math>\mathrm{OPT} + \mathcal{O}(OPT^\alpha)</math> bins, with run-time in <math>O(T(FOPT^{(1-\alpha)},n))</math>, where <math>\alpha\in(0,1)</math> is a constant.
* At most <math>(1+\epsilon)\mathrm{OPT} + \mathcal{O}(\epsilon^{-2})</math> bins, with run-time in <math>O(T(\epsilon^{-2},n))</math>, where <math>\epsilon>0</math> is a constant.
== Algorithm ==
== References ==
| |||