Content deleted Content added
LiranKatzir (talk | contribs) ←Created page with 'The maximum general assignment problem is a problem in combinatorial optimization. This problem is a generalization of the assignment problem in which both task an...' |
LiranKatzir (talk | contribs) |
||
Line 17:
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>.
== Greedy approximation algorithm ==
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 ''x<sub>i</sub>'' for bin ''b<sub>j</sub>'' is ''p<sub>ij</sub>'' is ''x<sub>i</sub>'' is not selected for any other bin or ''p<sub>ij</sub> - p<sub>ik</sub>'' if ''x<sub>i</sub>'' is selected for bin ''b<sub>k</sub>''.
Formally:
: For ''j=1..m'' do:
:: find the optimal solution to bin ''b<sub>j</sub>'' using the residual profit funtion
| |||