Content deleted Content added
LiranKatzir (talk | contribs) No edit summary |
LiranKatzir (talk | contribs) |
||
Line 13:
The generalized assignment problem is NP-hard, and it is even APX-hard to approximation. Recently it was shown that it is (<math>\frac{e}{e-1} - \epsilon</math>) hard to approximate for every <math>\epsilon</math>.
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} – p_{ik} </math> if <math>x_i</math> is selected for bin <math>b_k</math>.
Formally:
| |||