Karmarkar–Karp bin packing algorithms: Difference between revisions

Revision as of 08:25, 13 January 2022

Revision as of 08:25, 13 January 2022

Line 46:

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. Then:

* In <math>K'</math> all items have the same size. In <math>K</math> the number of different sizes is <math>m(K) = 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.

Line 56:

* 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. Let <math>K := \cup _r K_r</math> and <math>K' := \cup _r K'_r</math>.

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

Then:

* <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.

and 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.

* Therefore, <math>OPT(K') \leq k\cdot \log_2(1/g)</math>.

* Therefore, <math>OPT(J) \leq OPT(K)+OPT(K')\leq OPT(K)+k\cdot \log_2(1/g)</math>.