Karmarkar–Karp bin packing algorithms: Difference between revisions

Revision as of 21:03, 12 January 2022

Revision as of 21:31, 12 January 2022

Line 44:

=== Linear grouping ===

Pick some integerLet ''<math>k>1</math>''. Orderbe thean items by descendinginteger sizeparameter. 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. Then: <blockquote><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. </blockquote>Therefore, <math>OPT(J) \leq OPT(K)+k</math>; 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.

* <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)+k</math>; 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:

TODO

* Partition the instance <math>J</math> into several instances <math>J_0, J_1, \ldots</math> such that, in each instance <math>J_r</math>, all sizes are in the interval <math>[B/2^{r+1}, B/2^r)</math>. Note that, if all items in <math>J</math> have size at least ''<math>g\cdot B</math>'', then the number of instances is at most <math>\log_2(1/g)</math>.

* On each instance <math>J_r</math>, perform linear rounding with paramter ''<math>k\cdot 2^r</math>''. Let <math>K_r, K'_r</math> be the resulting instances.

=== Alternative geometric grouping ===