Content deleted Content added
m Open access bot: arxiv updated in citation with #oabot. |
m →The integral LP: fix math formulas not rendered inline because of missing newlines around blockquote |
||
Line 15:
* ''x<sub>c</sub>'' - a variable denoting the number of bins with configuration ''c''.
Then, the '''configuration LP of bin-packing''' is:
<blockquote>
<math>\sum_{c\in C}a_{s,c}x_c \geq n_s</math> for all ''s'' in ''S'' (- all ''n<sub>s</sub>'' items of size ''s'' are packed). ▼
minimize <math>\sum_{c\in C}x_c</math> subject to
▲<math>\sum_{c\in C}a_{s,c}x_c \geq n_s</math> for all ''s'' in ''S'' (
<math>x_c\in\{0,\ldots,n\}</math> for all ''c'' in ''C'' (- there are at most ''n'' bins overall, so at most ''n'' of each individual configuration). </blockquote>The configuration LP is an [[integer linear program]], so in general it is NP-hard. Moreover, even the problem itself is generally very large: it has ''C'' variables and ''S'' constraints. If the smallest item size is ''eB'' (for some fraction ''e'' in (0,1)), then there can be up to 1/''e'' items in each bin, so the number of configurations ''C'' ~ ''S''<sup>1/''e''</sup>, which can be very large if ''e'' is small (if e is considered a constant, then the integer LP can be solved by exhaustive search: there are at most ''S<sup>1/e</sup>'' configurations, and for each configuration there are at most ''n'' possible values, so there are at most <math> n^{S^{1/e}}</math> combinations to check. For each combination, we have to check ''S'' constraints, so the run-time is <math>S\cdot n^{S^{1/e}}</math>, which is polynomial in ''n'' when ''S, e'' are constant).<ref name=":2" />▼
<math>x_c\in\{0,\ldots,n\}</math> for all ''c'' in ''C'' (there are at most ''n'' bins overall, so at most ''n'' of each individual configuration).
</blockquote>
▲
However, this ILP serves as a basis for several approximation algorithms. The main idea of these algorithms is to reduce the original instance into a new instance in which ''S'' is small and ''e'' is large, so ''C'' is relatively small. Then, the ILP can be solved either by complete search (if ''S'', ''C'' are sufficiently small), or by relaxing it into a ''fractional'' LP.
| |||