Content deleted Content added
LiranKatzir (talk | contribs) |
LiranKatzir (talk | contribs) |
||
Line 14:
Using any <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>.
Formally:
| |||