Karmarkar–Karp bin packing algorithms: Difference between revisions

Revision as of 10:10, 14 January 2022

Revision as of 10:30, 14 January 2022

Line 16:

Obviously, FOPT(''I'') ≤ OPT(I).

== High-level ideascheme ==

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.

Line 142:

</math> times. If we choose the constraints to remove at random, then the expected number of iterations is <math> O(m)\cdot[1 + \ln(Q/m)]</math>.

Finally, we have a reduced dual LP, with only ''m'' variables and ''m'' constraints. The optimal value of the reduced LP is at least <math> LOPT-\epsilonh</math>, where <math>\epsilonh \approx \delta\cdot [(Q/m) + m\ln(Q/m)]</math>.

=== Solving the primal LP ===

By the [[Dual linear program|LP duality theorem]], the minimum value of the primal LP equals the maximum value of the dual LP, which we denoted by LOPT. Once we have a reduced dual LP, we take its dual, and take a reduced primal LP. This LP has only ''m'' variables - corresponding to only ''m'' out of ''C'' configurations. The maximum value of the reduced dual LP is at least <math> LOPT-\epsilonh</math>. It can be shown{{Clarify|date=January 2022}} that the optimal solution of the reduced primal LP is at most <math> LOPT+\epsilonh</math>. The solution gives a near-optimal bin packing, using at most ''m'' configurations.

The total run-time of the deterministic algorithm, when all items are larger than ''<math>g\cdot B</math>, is:''

Line 157:

\right)

\approx

O\left(m^8 \ln{m} \ln^2(\frac{m n}{g \epsilonh}) + \frac{m^4 n \ln{m}}{\epsilonh}\ln(\frac{m n}{g \epsilonh}) \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 \epsilonh}) + \frac{m^4 n \log{m}}{\epsilonh}\log(\frac{m n}{g \epsilonh}) \right)</math>.

== GuaranteesEnd-to-end algorithms ==

Karmarkar and Karp presented fourthree algorithms, that use the above techniques with different algorithmsparameters. 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 [[configurationfractional linearLP program]]: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>. The algorithms attain the following guarantees:

=== Algorithm 1 ===

Let <math>\epsilon>0</math> be a constant representing the desired approximation accuracy.

*1-a. Set <math>g = \max(1/n, \epsilon/2)</math>. Let <math>J</math> be an instance constructed from <math>I</math> by removing all items smaller than ''g''.

**2-a. Set <math>k = n\cdot \epsilon^2</math>. Let <math>K</math> be an instance constructed from <math>J</math> by linear grouping with parameter ''k'', and let ''<math>K'</math>'' be the remaining instance (the group of ''k'' largest items). Note that <math>m(K) \leq n/k + 1 \approx 1/\epsilon^2</math>.

***3-a. Construct the configuration linear program for <math>K</math>, without the integrality constraints.

****4. Compute a solution '''x''' for <math>K</math>, with tolerance ''h''=1. The result is a fractional bin packing with <math>b_L\leq LOPT(K)+1</math> bins.

***3-b. Round '''x''' to an integral solution for <math>K</math>. The number of bins is <math>b_K\leq b_L + m(K)/2 \leq LOPT(K)+1 + 1/2\epsilon^2</math>.

**2-b. Add at most ''k'' bins for the items in ''<math>K'</math>''; get a packing of <math>J</math>. The number of bins is <math>b_J\leq b_K+k \leq LOPT(K)+1 + 1/2\epsilon^2 + n\cdot \epsilon^2</math>.

*1-b. Add the items smaller than ''g'' to get a solution for <math>I</math>. The number of bins is: <math>b_I \leq \max(b_J, (1+2 g)\cdot OPT(I) + 1)\leq (1+\epsilon)OPT(I) + 1/2\epsilon^2 + 3</math>.

*All Atin mostall, the number of bins is in <math>(1+\epsilon)\mathrm{OPT} + \mathcal{O}(\epsilon^{-2})</math> bins,and withthe run-time is in <math>O(T(\epsilon^{-2},n))</math>,. where <math>\epsilon>0</math> is a constant.

=== Algorithm 2 ===

* 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.

== Improvements ==