Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
1143373 | Operations Research Letters | 2006 | 6 Pages |
Abstract
We give a (1–1/e1/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.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Zeev Nutov, Israel Beniaminy, Raphael Yuster,