Content deleted Content added
Citation bot (talk | contribs) Add: publisher, authors 1-1. Removed parameters. Some additions/deletions were parameter name changes. | Use this bot. Report bugs. | Suggested by Corvus florensis | #UCB_webform 1540/2500 |
→Further reading: +* |
||
| (5 intermediate revisions by 5 users not shown) | |||
Line 22:
== Complexity ==
The generalized assignment problem is [[NP-hard]]
| last1 = Özbakir | first1 = Lale
| last2 = Baykasoğlu | first2 = Adil
Line 33:
| volume = 215
| issue = 11
| year = 2010}}.</ref> However, there are linear-programming relaxations which give a <math>(1 - 1/e)</math>-approximation.<ref>{{cite
==Greedy approximation algorithm==
For the problem variant in which not every item must be assigned to a bin, there is a family of algorithms for solving the GAP by using a combinatorial translation of any algorithm for the knapsack problem into an approximation algorithm for the GAP.<ref>{{cite journal |doi=10.1016/j.ipl.2006.06.003|title=An efficient approximation for the Generalized Assignment Problem|journal=Information Processing Letters|volume=100|issue=4|pages=162–166|year=2006|last1=Cohen|first1=Reuven|last2=Katzir|first2=Liran|last3=Raz|first3=Danny|citeseerx=10.1.1.159.1947}}</ref>
Using any <math>\alpha</math>-approximation algorithm ALG for the [[knapsack problem]], it is possible to construct a (<math>\alpha + 1</math>)-approximation for the generalized assignment problem in a greedy manner using a residual profit concept.
Line 58:
==Further reading==
* {{cite book |isbn=978-3-540-24777-7|title=Knapsack Problems|last1=Kellerer|first1=Hans|last2=Pferschy|first2=Ulrich|last3=Pisinger|first3=David|date=2013-03-19|publisher=Springer }}
[[Category:NP-complete problems]]
| |||