Karmarkar–Karp bin packing algorithms: Difference between revisions

Revision as of 21:44, 12 January 2022

Revision as of 08:25, 13 January 2022

Line 44:

=== Linear grouping ===

Let ''<math>k>1</math>'' be an integer parameter. Put the largest ''<math>k</math> ''items in group 1; the next-largest ''<math>k</math> ''items in group 2; and so on (the last group might have fewer than ''<math>k</math> ''items). Let <math>J</math> be the original instance. Let <math>K'</math> be the first group (the group of the ''<math>k</math> ''largest items), and <math>K</math> the grouped instance ''without'' the first group. Note that in <math>K'</math> all items have the same size, and in <math>K</math> the number of different sizes is <math>n/k</math>. Then:

* In <math>K'</math> all items have the same size. In <math>K</math> the number of different sizes is <math>n/k</math>.
*<math>OPT(K) \leq OPT(J)</math> - since group 1 in <math>J</math> dominates group 2 in <math>K</math> (all ''k'' items in group 1 are larger than the ''k'' items in group 2); similarly, group 2 in <math>J</math> dominates group 3 in <math>K</math>, etc.

* <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\cup K') \leq OPT(K)+OPT(K') \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.