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

Zeev Nutov, Israel Beniaminy, Raphael Yuster

פרסום מחקרי: פרסום בכתב עתמאמרביקורת עמיתים


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.

שפה מקוריתאנגלית
עמודים (מ-עד)283-288
מספר עמודים6
כתב עתOperations Research Letters
מספר גיליון3
מזהי עצם דיגיטלי (DOIs)
סטטוס פרסוםפורסם - מאי 2006

טביעת אצבע

להלן מוצגים תחומי המחקר של הפרסום 'A (1-1/e)-approximation algorithm for the generalized assignment problem'. יחד הם יוצרים טביעת אצבע ייחודית.

פורמט ציטוט ביבליוגרפי