Generalized assignment problem: Difference between revisions

Revision as of 10:34, 10 February 2017

Revision as of 10:46, 10 February 2017

Line 18:

== Complexity ==

The generalized assignment problem is [[NP-hard]]<ref>{{citation

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}}

| last1 = Özbakir | first1 = Lale

| last2 = Baykasoğlu | first2 = Adil

| last3 = Tapkan | first3 = Pınar

| pages = 3782–3795

| publisher = Elsevier

| series = Applied Mathematics and Computation

| title = Bees algorithm for generalized assignment problem

| url = http://www.sciencedirect.com/science/article/pii/S0096300309010078

| volume = 215

The | generalizedyear assignment= problem is [[NP-hard]]2010}}.</ref>, 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}}

==Greedy approximation algorithm==