Karmarkar–Karp bin packing algorithms: Difference between revisions

Revision as of 10:30, 14 January 2022

Revision as of 11:28, 14 January 2022

Line 168:

**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. The run-time is <math>T(m(K),n(K)) \leq T(\epsilon^{-2},n) </math>.

***3-b. Round '''x''' to an integral solution for <math>K</math>. Add at most <math>m(K)/2</math> bins for the fractional part. The total 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 forPack the items in ''<math>K'</math>'' using at most ''k'' bins; 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 in all, the number of bins is in <math>(1+\epsilon)OPT + O(\epsilon^{-2})</math> and the run-time is in <math>O(n\log n + T(\epsilon^{-2},n))</math>.

=== Algorithm 2 ===

*Let At most <math>\mathrm{OPT} + \mathcal{O}(\log^2 OPT)g>0</math> bins,be witha run-timereal inparameter and <math>O(T(FOPT,n))k>0</math> an integer parameter to be determined later.

*1-a. Let <math>J</math> be an instance constructed from <math>I</math> by removing all items smaller than ''g''.

*2. While <math>FOPT(J) > 1+\frac{k}{k-1}\ln(1/g)</math> do:

**2-a. Do the Alternative Geometric Grouping with parameter ''k''. Let <math>K</math> be the resulting instance, and let ''<math>K'</math>'' be the remaining instance. We have <math>m(K) \leq FOPT(J)/k + \ln(1/g)</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. The run-time is <math>T(m(K),n(K)) \leq T(FOPT(J)/k + \ln(1/g) ,n) </math>.

***3-b. Round '''x''' to an integral solution for <math>K</math>. Do ''not'' add bins for the fractional part. Instead, just remove the packed items from <math>J</math>.

**2-b. Pack the items in ''<math>K'</math>'' in at most ''<math>2 k\cdot (2 + \ln(1/g))</math>'' bins.

*2. Once <math>FOPT(J) \leq 1+\frac{k}{k-1}\ln(1/g)</math>, pack the remaining items greedily into at most <math>2 FOPT(J) \leq 2+\frac{2 k}{k-1}\ln(1/g)</math> bins. The total number of bins used for <math>J</math> is: <math>b_J \leq OPT(I) + \left[1+\frac{\ln(FOPT(I))}{\ln k}\right]\left[1 + 4k + 2k\ln(1/g)\right]+ 2 + \frac{2}{1-\frac{1}{k}\ln(1/g)}</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)</math>.

The run-time is in <math>O(n\log n + T(FOPT(J)/k + \ln(1/g),n))</math>.

Now, if we choose ''k''=2 and ''g''=1/FOPT(I), we get:

<math>b_J \leq OPT + O(\log^2(FOPT)) </math>, and similarly <math>b_I \leq \max(b_J, OPT+2OPT /FOPT+1) \in OPT+\log^2(OPT) \leq \max(b_J, OPT+5)</math>, so the total number of bins is in <math>OPT + O(\log^2(FOPT))</math>. The run-time is <math>T(FOPT/2 + \ln(FOPT) ,n)\in 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.