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

بصمة

أدرس بدقة موضوعات البحث “A (1-1/e)-approximation algorithm for the generalized assignment problem'. فهما يشكلان معًا بصمة فريدة.

قم بذكر هذا