Content deleted Content added
Erel Segal (talk | contribs) |
Erel Segal (talk | contribs) |
||
Line 17:
* ''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 martix '''''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):
*1-a. Let <math>J</math> be an instance constructed from <math>I</math> by removing small items.
**2-a. Let <math>K</math> be an instance constructed from <math>J</math> by grouping items and rounding the size of items in each group to the highest item in the group.
***3-a. Construct the configuration linear program for <math>K</math>, without the integrality constraints.
****4. Compute a (fractional) solution '''x''' for the relaxed linear program.
***3-b. Round '''x''' to an integral solution for <math>K</math>.
**2-b. "Un-group" the items to get a solution for <math>J</math>.
*1-b. Add the small items to get a solution for <math>I</math>.
Below, we describe each of these steps in turn.
== 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 ''g'', and remove from <math>I</math> all items whose size is less than ''g''. 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>(1-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+2 g) OPT+1</math>.
== Fractional bin packing ==
| |||