Content deleted Content added
Erel Segal (talk | contribs) |
Erel Segal (talk | contribs) |
||
Line 44:
=== Linear grouping ===
Pick some integer ''<math>k>1</math>''. Order the items by descending size. 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.
=== Geometric rounding ===
TODO
=== Alternative geometric rounding ===
TODO
== Fractional bin packing ==
| |||