Karmarkar–Karp bin packing algorithms: Difference between revisions

Revision as of 08:25, 13 January 2022

Revision as of 08:26, 13 January 2022

Line 58:

Then, the number of different sizes is bounded as follows:

* For all ''r'', <math>m(K'_r) = 1</math> - since <math>K'_r</math> has ''<math>k\cdot 2^r</math>'' items, and all of them are smaller than <math>B/2^r</math>, so they can be packed into at most ''<math>k</math> ''bins.

andAnd the number of bins is bounded as follows:

* For all ''r'', <math>OPT(K'_r) \leq k</math> - since <math>K'_r</math> has ''<math>k\cdot 2^r</math>'' items, and all of them are smaller than <math>B/2^r</math>, so they can be packed into at most ''<math>k</math> ''bins.