کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6874255 | 686948 | 2015 | 6 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Packing items into several bins facilitates approximating the separable assignment problem
ترجمه فارسی عنوان
آیتم های بسته بندی را به چند سطل تسهیل می کند تقریبا مشکل انتساب جدا می شود
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
مشکل تکلیف جداگانه الگوریتم های تقریبی، گرد شدن تصادفی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
In this paper, we consider the case of SAP where each item may be assigned at most kâ¥1 times (but at most once to each bin) and present a ((1â1ek)β)-approximation algorithm for this case under the assumption that the single bin subproblem admits a β-approximation algorithm. If the single bin subproblem admits an FPTAS, we obtain a (1â1ek)-approximation, which shows that, for kâ¥2, the problem admits approximation algorithms that beat the upper bound of (1â1e) known for other special cases of SAP.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information Processing Letters - Volume 115, Issues 6â8, JuneâAugust 2015, Pages 570-575
Journal: Information Processing Letters - Volume 115, Issues 6â8, JuneâAugust 2015, Pages 570-575
نویسندگان
Marco Bender, Clemens Thielen, Stephan Westphal,