Karmarkar–Karp bin packing algorithms: Difference between revisions

Revision as of 16:04, 29 April 2023

Latest revision as of 16:27, 26 August 2025

(6 intermediate revisions by 4 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 22:

The KK algorithms essentially solve the [[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~~~\text{and}~~ \mathbf{x}~\text{is an integer}~</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_c'' of '''x''' represents the number of times configuration ''c'' is used.

* ''Example'':<ref name=":22">{{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> suppose the item sizes are 3,3,3,3,3,4,4,4,4,4, and ''B''=12. Then there are ''C''=10 possible configurations: 3333; 333; 33, 334; 3, 34, 344; 4, 44, 444. The matrix '''''A''''' has two rows: [4,3,2,2,1,1,1,0,0,0] for s=3 and [0,0,0,1,0,1,2,1,2,3] for s=4. The vector '''n''' is [5,5] since there are 5 items of each size. A possible optimal solution is '''x'''=[1,0,0,0,0,0,1,0,0,1], corresponding to using three bins with configurations 3333, 344, 444.

There are two main difficulties in solving this problem. First, it is an [[Integer programming|integer linear program]], which is computationally hard to solve. Second, the number of variables is ''C'' - the number of configurations, which may be enormous. The KK algorithms cope with these difficulties using several techniques, some of which were already introduced by de-la-Vega and Lueker.<ref name=":0" /> Here is a high-level description of the algorithm (where <math>I</math> is the original instance):

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 journalbook|last=Rothvoß|first=T.|datetitle=2013-10-01 IEEE 54th Annual Symposium on Foundations of Computer Science |titlechapter=Approximating Bin Packing within O(log OPT *· Log Log OPT) Bins |url=https://ieeexplore.ieee.org/document/6686137|journaldate=2013 IEEE 54th Annual Symposium on Foundations of Computer Science-10-01|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 ==