|
== Step 3. Constructing and rounding the LP ==
TheWe main tool used byconsider the KK algorithms is the fractional [[configuration linear program]] without the integrality constraints:<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'''''we 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''' isare allowed to beuse fractional, the solution might be smaller; denote it by LOPT. Moreover, let ''FOPT'' = (''a ''<sub>1</sub>+...+''a<sub>n</sub>'')/''B'' = the theoretically-optimalfractional number of bins,each when all bins are completely filled with items or item fractionsconfiguration. The following relations are obvious:
* ''Example'': suppose there are 31 items of size 3 and 7 items of size 4, and the bin-size is 10. The configurations are: 4, 44, 34, 334, 3, 33, 333. The constraints are [0,0,1,2,1,2,3]*'''x'''=31 and [1,2,1,1,0,0,0]*'''x'''=7. An optimal solution to the fractional LP is [0,0,0,7,0,0,17/3] That is: there are 7 bins of configuration 334 and 17/3 bins of configuration 333. Note that only two different configurations are needed.
Denote the optimal solution of the linear program by LOPT. The following relations are obvious:
* FOPT(I) ≤ LOPT(I), since FOPT(I) is the (possibly fractional) number of bins when all bins are completely filled with items or fractions of items. Clearly, no solution can be more efficient.
|
