TY - JOUR
T1 - A (1-1/e)-approximation algorithm for the generalized assignment problem
AU - Nutov, Zeev
AU - Beniaminy, Israel
AU - Yuster, Raphael
PY - 2006/5
Y1 - 2006/5
N2 - We give a (1-1/e)-approximation algorithm for the max-profit generalized assignment problem (Max-GAP) with fixed profits when the profit (but not necessarily the size) of every item is independent from the bin it is assigned to. The previously best-known approximation ratio for this problem was 12.
AB - We give a (1-1/e)-approximation algorithm for the max-profit generalized assignment problem (Max-GAP) with fixed profits when the profit (but not necessarily the size) of every item is independent from the bin it is assigned to. The previously best-known approximation ratio for this problem was 12.
KW - Approximation algorithm
KW - Generalized assignment
UR - http://www.scopus.com/inward/record.url?scp=32644445035&partnerID=8YFLogxK
U2 - 10.1016/j.orl.2005.05.006
DO - 10.1016/j.orl.2005.05.006
M3 - ???researchoutput.researchoutputtypes.contributiontojournal.article???
AN - SCOPUS:32644445035
SN - 0167-6377
VL - 34
SP - 283
EP - 288
JO - Operations Research Letters
JF - Operations Research Letters
IS - 3
ER -