Generalized assignment problem: Difference between revisions

Revision as of 12:43, 1 July 2014

Revision as of 15:41, 5 August 2014

Line 20:

==Greedy approximation algorithm==

Using any algorithm ALG <math> \alpha</math>-approximation algorithm ALG 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.