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

Zeev Nutov; Israel Beniaminy; Raphael Yuster

doi:10.1016/j.orl.2005.05.006

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
כרך	34
מספר גיליון	3
מזהי עצם דיגיטלי (DOIs)	https://doi.org/10.1016/j.orl.2005.05.006
סטטוס פרסום	פורסם - מאי 2006

גישה למסמך

10.1016/j.orl.2005.05.006

קבצים וקישורים אחרים

Link to publication in Scopus

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

@article{fee8a72949854641ba7736160ea4e3d5,

title = "A (1-1/e)-approximation algorithm for the generalized assignment problem",

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 12.",

keywords = "Approximation algorithm, Generalized assignment",

author = "Zeev Nutov and Israel Beniaminy and Raphael Yuster",

year = "2006",

month = may,

doi = "10.1016/j.orl.2005.05.006",

language = "אנגלית",

volume = "34",

pages = "283--288",

journal = "Operations Research Letters",

issn = "0167-6377",

publisher = "Elsevier BV",

number = "3",

}

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 - https://www.scopus.com/pages/publications/32644445035

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 -

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

תקציר

גישה למסמך

קבצים וקישורים אחרים

טביעת אצבע

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