Content deleted Content added
m clean up /fixed checkwiki error 18 using AWB (8717) |
Badgerific (talk | contribs) |
||
Line 20:
==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 during iteration <math>j</math> a tentative selection of items to bin <math>b_j</math> is selected.
The selection for bin <math>b_j</math> might change as items might be reselected in a later iteration for other bins.
| |||