Content deleted Content added
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) - \varepsilon</math> hard to approximate for every <math>\varepsilon</math>.{{Citation needed}}
==Greedy approximation algorithm==
| |||