Generalized assignment problem: Difference between revisions

Revision as of 17:30, 10 January 2012

Revision as of 09:32, 19 March 2012

Line 17:

::<math> x_{ij} \in \{0,1\} \qquad i=1, \ldots, m, \quad j=1, \ldots, n</math>;

The generalized assignment problem is [[NP-hard]], and it is even [[APX-hard]] to approximate it. Recently it was shown that an extension of it is (<math>e/(e-1) - \epsilonvarepsilon</math>) hard to approximate for every <math>\epsilonvarepsilon</math>.

==Greedy approximation algorithm==