Content deleted Content added
LiranKatzir (talk | contribs) No edit summary |
LiranKatzir (talk | contribs) |
||
Line 16:
Using any algorithm ALG <math> \alpha</math>-approximation algorithm for the knapsack problem, it is possible to construct a (<math> \alpha+1</math>)-approximation for the generalized assignment problem in a greedy manner using a residual profit concept.
The residual profit of an item <math>x_i</math> for bin <math>b_j</math> is <math>p_{ij}</math> is <math>x_i</math> is not selected for any other bin or <math> p_{ij}</math> – <math>p_{ik} </math> if <math>x_i</math> is selected for bin <math>b_k</math>.
Mathematically the generalized assignment problem can be formulated as:
:maximize <math>\sum_{i=1}^m\sum_{j=1}^n p_{ij} x_{ij}.</math>
:subject to <math>\sum_{j=1}^n w_{ij} x_{ij} \le w_i \qquad i=1, \ldots, m</math>;
::<math> \sum_{i=1}^m x_{ij} \leq 1 \qquad j=1, \ldots, n</math>;
::<math> x_{ij} \in \{0,1\} \qquad i=1, \ldots, m, \quad j=1, \ldots, n</math>;
Formally:
| |||