کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
431613 688594 2015 10 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
A faster algorithm for the resource allocation problem with convex cost functions
ترجمه فارسی عنوان
معرفی یک الگوریتم سریع تر برای مساله تخصیص منابع با توابع هزینه محدب
کلمات کلیدی
الگوریتم های چندجمله ای؛ تجزیه و تحلیل پیچیدگی؛ ساختار داده ها؛ بهینه سازی ترکیبی غیر خطی
فهرست مطالب مقاله
چکیده
کلمات کلیدی
1.مقدمه
2 . الگوریتم ساده
3 . الگوریتم دو فازی
شکل 1: تصویر الگوریتم دو فازی
3.1 یک مثال ساده
4 . الگوریتم چندفازی
5 . مطالعات محاسباتی
5.1 مساله بازپرسازی مشترک
جدول 1: عملکرد الگوریتم چندفازی برای مساله بازپرسازی مشترک. زمان اجرا(T)، کاهش زمان(T_reduct) و مقدار هدف بهینه(OPT).
6 . نتیجه گیری پایانی
ترجمه چکیده
در اینجا، به بازنگری مساله تخصیص منابع کلاسیک با توابع هدف محدب عمومی و با در نظر گرفتن قید کوله پشتی عدد صحیح خواهیم پرداخت. این دسته از مسائل، پایه و اساس بهینه سازی گسسته را تشکیل می دهند و کاربردهای وسیع و گسترده ای دارند. در مقاله پیش رو، الگوریتم تقسیم-و-غلبه زمان چندجمله ای جدیدی به نام الگوریتم چندفازی را معرفی می نماییم و ثابت می کنیم که پیچیدگی محاسباتی این الگوریتم برابر با O(n log n lob N) می باشد، و عملکرد آن از شناخته شده ترین الگوریتم زمان چندجمله ای که دارای پیچیدگی محاسباتی O(n(log N)2) است بهتر خواهد بود.
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش مقاله
معرفی یک الگوریتم سریع تر برای مساله تخصیص منابع با توابع هزینه محدب
چکیده انگلیسی
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).
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Discrete Algorithms - Volume 34, September 2015, Pages 137–146
نویسندگان
, , ,