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
المعرِّفات الرقمية للأشياء	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

ملخص

الوصول إلى المستند

الملفات والروابط الأخرى

بصمة

قم بذكر هذا