Content deleted Content added
Erel Segal (talk | contribs) |
Erel Segal (talk | contribs) No edit summary |
||
Line 49:
* <math>OPT(K') \leq k</math> - since it is possible to pack each item in <math>K'</math> into a single bin.
Therefore, <math>OPT(J) \leq OPT(K\cup K') \leq OPT(K)+OPT(K') \leq OPT(K)+k</math>. Indeed, given a solution to <math>K</math> with <math>b_K</math> bins, we can get a solution to <math>J</math> with at most <math>b_K+k</math> bins.
=== Geometric grouping ===
Let ''<math>k>1</math>'' be an integer parameter. Geometric grouping proceeds in two steps:
* 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 paramter ''<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:
* <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.
* Therefore, <math>OPT(K') \leq k\cdot \log_2(1/g)</math>.
* Therefore, <math>OPT(J) \leq OPT(K)+OPT(K')\leq OPT(K)+k\cdot \log_2(1/g)</math>.
=== Alternative geometric grouping ===
Line 60 ⟶ 65:
== Step 3. Constructing and rounding the LP ==
The main tool used by the KK algorithms is the fractional [[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</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<sub>c</sub>'' of '''x''' represents the number of times configuration ''c'' is used. If '''x''' is integral then the solution to this problem is exactly OPT. Since '''x''' is allowed to be fractional, the solution might be smaller; denote it by LOPT. Moreover, let ''FOPT'' = (''a''<sub>1</sub>+...+''a<sub>n</sub>'')/''B'' = the theoretically-optimal number of bins, when all bins are completely filled with items or item fractions. The following relations are obvious:
| |||