A (1−1/e)-approximation algorithm for the generalized assignment problem

0.00 Avg rating—0 Votes

Article ID:	iaor20062904
Country:	Netherlands
Volume:	34
Issue:	3
Start Page Number:	283
End Page Number:	288
Publication Date:	May 2006
Journal:	Operations Research Letters
Authors:	Nutov Zeev, Beniaminy Israel, Yuster Raphael
Keywords:	heuristics, combinatorial analysis

Abstract:

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 ½.

Reviews

Required fields are marked *. Your email address will not be published.