Content deleted Content added
Erel Segal (talk | contribs) |
Erel Segal (talk | contribs) |
||
Line 31:
== 1. Removing and adding small items ==
The motivation for removing small items is that, when all items are large, the number of items in each bin must be small, so the number of possible configurations is (relatively) small. We pick some constant ''<math>g\in(0,1)</math>'', and remove from the original instance <math>I</math> all items smaller than ''<math>g\cdot B</math>''. Let <math>J</math> be the resulting instance. Note that in <math>J</math>, each bin can contain at most ''<math>1/g</math>'' items. We pack <math>J</math> and get a packing with some <math>b_J</math> bins.
Now, we add the small items into the existing bins in an arbitrary order, as long as there is room. When there is no more room in the existing bins, we open a new bin (as in [[next-fit bin packing]]). Let <math>b_I</math> be the number of bins in the final packing. Then: <blockquote><math>b_I \leq \max(b_J, (1+2 g)\cdot OPT(I) + 1)</math>.</blockquote>''Proof''. If no new bins are opened, then the number of bins remains <math>b_J</math>. If a new bin is opened, then all bins except maybe the last one contain a total size of at least <math>B - g\cdot B</math>, so the total instance size is at least <math>(1-g)\cdot B\cdot (b_I-1)</math>. So the optimal solution needs at least <math>(1-g)\cdot (b_I-1)</math> bins. Therefore, <math>b_I \leq OPT/(1-g) + 1 = (1+g+g^2+\ldots) OPT+1 \leq (1+2g) OPT+1</math>.
== 2. Grouping and un-grouping items ==
The motivation for grouping items is to reduce the number of different item sizes, to reduce the number of constraints in the configuration LP.
* Order the items by descending size.
* Partition the items into groups.
* For each group, modify the size of all items in the group to the largest size in the group.
There are several different grouping methods.
=== 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).
== Fractional bin packing ==
| |||