Content deleted Content added
LiranKatzir (talk | contribs) |
LiranKatzir (talk | contribs) |
||
Line 21:
==Greedy Approximation Algorithm==
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 algorithm constructs a schedule in iterations, where in iteration <math>
The selection for bin <math>b_j</math> might change as items might be reselected in a later iteration for other bins.
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>.
| |||