Generalized assignment problem: Difference between revisions

Revision as of 19:15, 23 December 2015

Revision as of 10:34, 10 February 2017

Line 17:

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

== Complexity ==

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|date=November 2012}}