Content deleted Content added
general assignment problem -> Generalized assignment problem |
LiranKatzir (talk | contribs) |
||
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 approximation. 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==
| |||