Karmarkar–Karp bin packing algorithms: Difference between revisions

Revision as of 21:31, 12 January 2022

Revision as of 21:34, 12 January 2022

Line 49:

* <math>OPT(K') \leq k</math> - since it is possible to pack each item in <math>K'</math> into a single bin.

Therefore, <math>OPT(J) \leq OPT(K)+k</math>;. Indeed, given a solution to <math>K</math> with <math>b_K</math> bins, we can get a solution to <math>J</math> with at most <math>b_K+k</math> bins.

=== Geometric grouping ===

Let ''<math>k>1</math>'' be an integer parameter. Geometric grouping proceeds in two steps: