دانلود مقاله ISI انگلیسی شماره 78949
عنوان فارسی مقاله

یک الگوریتم سریع تر برای مشکل تخصیص منابع با توابع هزینه محدب

کد مقاله سال انتشار مقاله انگلیسی ترجمه فارسی تعداد کلمات
78949 2015 10 صفحه PDF سفارش دهید محاسبه نشده
خرید مقاله
پس از پرداخت، فوراً می توانید مقاله را دانلود فرمایید.
عنوان انگلیسی
A faster algorithm for the resource allocation problem with convex cost functions
منبع

Publisher : Elsevier - Science Direct (الزویر - ساینس دایرکت)

Journal : Journal of Discrete Algorithms, Volume 34, September 2015, Pages 137–146

کلمات کلیدی
الگوریتم های چندجمله ای؛ تجزیه و تحلیل پیچیدگی؛ ساختار داده ها؛ بهینه سازی ترکیبی غیر خطی
پیش نمایش مقاله
پیش نمایش مقاله یک الگوریتم سریع تر برای مشکل تخصیص منابع با توابع هزینه محدب

چکیده انگلیسی

We revisit the classical resource allocation problem with general convex objective functions, subject to an integer knapsack constraint. This class of problems is fundamental in discrete optimization and arises in a wide variety of applications. In this paper, we propose a novel polynomial-time divide-and-conquer algorithm (called the multi-phase algorithm) and prove that it has a computational complexity of O(nlog⁡nlog⁡N)O(nlog⁡nlog⁡N), which outperforms the best known polynomial-time algorithm with O(n(log⁡N)2)O(n(log⁡N)2).

خرید مقاله
پس از پرداخت، فوراً می توانید مقاله را دانلود فرمایید.