Karmarkar–Karp bin packing algorithms: Difference between revisions

Revision as of 08:26, 13 January 2022

Revision as of 08:43, 13 January 2022

Line 11:

**''n_i'' is the number of items of size ''s_i''.

* ''B'' - the bin size.

Given an instance ''I'', we denote:

*OPT(I) = the optimal solution of instance ''I''.

*FOPT(''I'') = (''a''₁+...+''a_n'')/''B'' = the theoretically-optimal number of bins, when all bins are completely filled with items or item fractions.

Obviously, FOPT(''I'') ≤ OPT(I).

== High-level idea ==

The KK algorithms essentially solve the [[configuration linear program]]:<blockquote><math>\text{minimize}~~\mathbf{1}\cdot \mathbf{x}~~~\text{s.t.}~~ A \mathbf{x}\geq \mathbf{n}~~~\text{and}~~ \mathbf{x}\geq 0~~~\text{and}~~ \mathbf{x}~\text{is an integer}~</math>.</blockquote>Here, '''''A''''' is a matrix with ''m'' rows. Each column of '''''A''''' represents a feasible ''configuration'' - a multiset of item-sizes, such that the sum of all these sizes is at most ''B''. The set of configurations is ''C''. '''x''' is a vector of size ''C.'' Each element ''x_c'' of '''x''' represents the number of times configuration ''c'' is used.

* ''Example'':<ref name=":22">{{Cite web|last=Claire Mathieu|title=Approximation Algorithms Part I, Week 3: bin packing|url=https://www.coursera.org/learn/approximation-algorithms-part-1/home/week/3|url-status=live|website=Coursera}}</ref> suppose the item sizes are 3,3,3,3,3,4,4,4,4,4, and ''B''=12. Then there are ''C''=10 possible configurations: 3333; 333; 33, 334; 3, 34, 344; 4, 44, 444. The martixmatrix '''''A''''' has two rows: [4,3,2,2,1,1,1,0,0,0] for s=3 and [0,0,0,1,0,1,2,1,2,3] for s=4. The vector '''n''' is [5,5] since there are 5 items of each size. A possible optimal solution is '''x'''=[1,0,0,0,0,0,1,0,0,1], corresponding to using three bins with configurations 3333, 344, 444.

There are two main difficulties in solving this problem. First, it is an [[Integer programming|integer linear program]], which is computationally hard to solve. Second, the number of variables is ''C'' - the number of configurations, which may be enormous. The KK algorithms cope with these difficulties using several techniques, some of which were already introduced by de-la-Vega and Lueker.<ref name=":0" /> Here is a high-level description of the algorithm (where <math>I</math> is the original instance):

Line 32 ⟶ 36:

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>. SoTherefore, <math>FOPT \geq (1-g)\cdot (b_I-1)</math>, so the optimal solution needs at least <math>(1-g)\cdot (b_I-1)</math> bins. Therefore,So <math>b_I \leq OPT/(1-g) + 1 = (1+g+g^2+\ldots) OPT+1 \leq (1+2g) OPT+1</math>.

== Step 2. Grouping and un-grouping items ==

Line 46 ⟶ 50:

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) =\leq n/k + 1</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 55 ⟶ 59:

* 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 paramterparameter ''<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:

* For all ''r'', <math>m(K'_r) = 1</math> - sinceand <math>K'_r</math>m(K_r) has\leq ''<math>n(J_r)/(k\cdot 2^r) + 1</math>''. items, andSince all ofitems themin <math>J_r</math> are smallerlarger than <math>B/2^{r+1}</math>, we have <math>n(J_r)\leq 2^{r+1} \cdot FOPT(J_r)</math>, so they<math>m(K_r) can\leq be2 packedFOPT(J_r)/k into+ at1</math>. Summing mostover all ''r'' gives <math>m(K) \leq 2 FOPT(J)/k + \log_2(1/g)</math> ''bins.

And theThe 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.