Content deleted Content added
Erel Segal (talk | contribs) |
Erel Segal (talk | contribs) |
||
Line 3:
== In bin packing ==
=== Definition ===
In the [[bin packing|bin packing problem]], there are ''n'' items with different sizes. The goal is to pack the items into a minimum number of bins of size ''B''. A ''feasible configuration'' is a set of sizes with a sum of at most ''B''. For example, suppose the item sizes are 3,3,3,3,3,4,4,4,4,4, and ''B''=12. Then the possible configurations are: 3333; 333; 33, 334; 3, 34, 344; 4, 44, 444. If we had only three items of size 3, then we could not use the 3333 configuration.
Line 15 ⟶ 17:
<math>\sum_{c\in C}a_{s,c}x_c \geq n_s</math> for every size ''s'' (- all ''n<sub>s</sub>'' items of size ''s'' are packed)
<math>x_c\in\{0,\ldots,n\}</math> (- there are at most ''n'' configurations of each type). </blockquote>
=== Solution === The configuration LP is an [[integer linear program]], so in general it is NP-hard. But in the special-special case in which the number of sizes is some constant ''S'', and each size is at least ''eB'' (for some constant fraction ''e''<1), there are at most 1/''e'' items in each bin, so the total number of configurations is at most ''S''<sup>1/''e''</sup>. Therefore, the configuration LP has at most ''S''<sup>1/''e''</sup> variables and ''S'' constraints, and it can be solved by exhaustive search in time <math>S\cdot n^{S^{1/e}}</math>, which is polynomial in ''n''.<ref>{{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> *
Line 22 ⟶ 27:
Finally, consider the general case in which there are also some small items, of size less than ''eB''. These items can be added greedily into the bins with the large items using e.g. [[Next-fit bin packing]]. If no new bins are created, then the number of bins is still at most (1+''e'')OPT. If new bins are created, this means that all bins (except maybe the last one) are full up to at least (1-''e'')''B''. Therefore, the number of bins is at most OPT/(1-''e'')+1, which is (1+O(''e''))OPT+1.
=== Fractional bin packing ===
The ''fractional configuration LP'' of bin-packing is the [[linear programming relaxation]] of the above ILP. It replaces the last constraint with the constraint
=== Improvements ===
This technique was later improved by several authors:
| |||