Generalized assignment problem: Difference between revisions

Revision as of 08:47, 23 November 2009

Revision as of 20:01, 11 January 2010

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 approximationapproximate it. Recently it was shown that an extension of it is (<math>e/(e-1) - \epsilon</math>) hard to approximate for every <math>\epsilon</math>.

==Greedy approximation algorithm==