Generalized assignment problem: Difference between revisions

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
Open access status updates in citations with OAbot #oabot
Line 36:
 
==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.