Karmarkar–Karp bin packing algorithms: Difference between revisions

Revision as of 17:20, 27 September 2023

Latest revision as of 16:27, 26 August 2025

(4 intermediate revisions by 3 users not shown)

Line 2:

{{Multiple issues|{{refimprove|date=March 2022}}{{more footnotes|date=March 2022}}}}

The '''Karmarkar–Karp''' ('''KK''') '''bin packing algorithms''' are several related [[approximation algorithm]] for the [[bin packing problem]].<ref name=":12">{{cite journalbook|last1=Karmarkar|first1=Narendra|last2=Karp|first2=Richard M.|datetitle=November23rd Annual Symposium on Foundations of Computer Science (SFCS 1982) |titlechapter=An efficient approximation scheme for the one-dimensional bin-packing problem |date=November 1982 |chapter-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|chapter-url-access=subscription}}</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 algorithms were considered a breakthrough in the study of bin packing: the previously-known algorithms found multiplicative approximation, where the number of bins was at most <math>r\cdot \mathrm{OPT}+s</math> for some constants <math>r>1, s>0</math>, or at most <math>(1+\varepsilon)\mathrm{OPT} + 1</math>.<ref name=":0">{{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> The KK algorithms were the first ones to attain an additive approximation.

Line 133:

* If the total value of the optimal knapsack solution is at most 1, then we say that '''y''' is feasible.

* If the total value of the optimal knapsack solution is larger than 1, then we say that '''y''' is infeasible, and the items in the optimal knapsack solution correspond to a configuration that violates a constraint (since <math>\mathbf{a}\cdot \mathbf{y} > 1</math> for the vector '''a''' that corresponds to this configuration).

The knapsack problem can be solved by [[dynamic programming]] in [[pseudo-polynomial time]]: <math>O(m\cdot V)</math>, where ''m'' is the number of inputs and ''V'' is the number of different possible values. To get a polynomial-time algorithm, we can solve the knapsack problem approximately, using input rounding. Suppose we want a solution with tolerance <math>\delta</math>. We can round each of <math>y_1,\ldots,y_m</math> down to the nearest multiple of ''<math>\delta</math>''/''n''. Then, the number of possible values between 0 and 1 is ''n''/''<math>\delta</math>'', and the run-time is <math>O(m n /\delta)</math>. The solution is at least the optimal solution minus ''<math>\delta</math>''/''n''.

=== Ellipsoid method with an approximate separation oracle ===

Line 164:

O\left(m^8 \ln{m} \ln^2(\frac{m n}{g h}) + \frac{m^4 n \ln{m}}{h}\ln(\frac{m n}{g h}) \right)</math>,

The expected total run-time of the [[randomized algorithm]] is: <math>O\left(m^7 \log{m} \log^2(\frac{m n}{g h}) + \frac{m^4 n \log{m}}{h}\log(\frac{m n}{g h}) \right)</math>.

== End-to-end algorithms ==

Karmarkar and Karp presented three algorithms, that use the above techniques with different parameters. The run-time of all these algorithms depends on a function <math>T(\cdot,\cdot)</math>, which is a polynomial function describing the time it takes to solve the fractional LP with tolerance ''h''=1, which is, for the deterministic version,<math>T(m,n)\in O(m^8\log{m}\log^2{n} + m^4 n \log{m}\log{n} )</math>.

Line 216:

The KK techniques were improved later, to provide even better approximations.

Rothvoss<ref name=":2">{{Cite book|last=Rothvoß|first=T.|title=2013 IEEE 54th Annual Symposium on Foundations of Computer Science |chapter=Approximating Bin Packing within O(log OPT · Log Log OPT) Bins |date=2013-10-01|chapter-url=https://ieeexplore.ieee.org/document/6686137|volume=|pages=20–29|arxiv=1301.4010|doi=10.1109/FOCS.2013.11|isbn=978-0-7695-5135-7|via=|s2cid=15905063}}</ref> uses the same scheme as Algorithm 2, but with a different rounding procedure in Step 2. He introduced a "gluing" step, in which small items are glued together to yield a single larger item. This gluing can be used to increase the smallest item size to about <math>B/\log^{12}(n)</math>. When all sizes are at least <math>B/\log^{12}(n)</math>, we can substitute <math>g = 1/\log^{12}(n)</math> in the guarantee of Algorithm 2, and get:<blockquote><math>b_J \leq OPT(I) + O(\log(FOPT)\log(\log(n)))</math>, </blockquote>which yields a <math>\mathrm{OPT} + O(\log(\mathrm{OPT})\cdot \log\log(\mathrm{OPT}))</math> bins.

Hoberg and Rothvoss<ref name=":3">{{Citation|last1=Hoberg|first1=Rebecca|title=A Logarithmic Additive Integrality Gap for Bin Packing|date=2017-01-01|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|last2=Rothvoss|first2=Thomas|s2cid=1647463|doi-access=free|arxiv=1503.08796}}</ref> use a similar scheme in which the items are first packed into "containers", and then the containers are packed into bins. Their algorithm needs at most <math>b_J \leq OPT(I) + O(\log(OPT))</math> bins.

== References ==