Karmarkar–Karp bin packing algorithms: Difference between revisions

Revision as of 11:11, 16 January 2022

Revision as of 21:05, 3 February 2022

Line 196:

Now, if we choose ''k''=2 and ''g''=1/FOPT(I), we get:<blockquote><math>b_J \leq OPT + O(\log^2(FOPT)) </math>, </blockquote>and hence:<blockquote><math>b_I \leq \max(b_J, OPT+2OPT /FOPT+1) \leq \max(b_J, OPT+5) \in OPT+\log^2(OPT)</math>, </blockquote>so the total number of bins is in <math>OPT + O(\log^2(FOPT))</math>. The run-time is <math>O(n\log n) + T(FOPT/2 + \ln(FOPT) ,n)\in O(n\log{n} + T(FOPT, n)) </math>.

The same algorithm can be used with different parameters to trade-off run-time with accuracy. For some parameter <math>\alpha\in(0,1)</math>, choose <math>k=FOPT^{\alpha}</math> and <math>g=1/FOPT^{1-\alpha}</math>. Then, the packing needs at most most <math>\mathrm{OPT} + \mathcal{O}(OPT^\alpha)</math> bins, and the run-time is in <math>O(n\log{n} + T(FOPT^{(1-\alpha)},n))</math>.

=== Algorithm 3 ===