Karmarkar–Karp bin packing algorithms: Difference between revisions

Revision as of 20:28, 12 January 2022

Revision as of 20:34, 12 January 2022

Line 30:

== 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. Initially, we pick some constant ''<math>g\in(0,1)</math>'', and remove from <math>I</math> all items whose size is less than ''<math>g\cdot B</math>''. Let <math>J</math> be the reduced instance. 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 resulting allocation. 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>(1B - 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 \leq= (1+g+g^2+\ldots) gOPT+1 \leq (1+2g) OPT+1</math>.

== Fractional bin packing ==