Content deleted Content added
Erel Segal (talk | contribs) No edit summary |
Erel Segal (talk | contribs) |
||
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:
* <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.
| |||