کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4946841 | 1439557 | 2017 | 12 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Fast centralized integer resource allocation algorithm and its distributed extension over digraphs
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
هوش مصنوعی
پیش نمایش صفحه اول مقاله
![عکس صفحه اول مقاله: Fast centralized integer resource allocation algorithm and its distributed extension over digraphs Fast centralized integer resource allocation algorithm and its distributed extension over digraphs](/preview/png/4946841.png)
چکیده انگلیسی
This paper studies the resource allocation problem with convex objective functions, subject to individual resource constraints, equality constraints, and integer constraints. The goal is to minimize the total cost when allocating the total resource D to n agents. We propose a novel min-heap and optimization relaxation based centralized algorithm and prove that it has a computational complexity of O(nlogn+nlogD) when the resource constraints of individual agents are [0, D], which outperforms the best known multi-phase algorithm with O(nlognlogD). By extending the centralized algorithm, we present a consensus based distributed optimization algorithm to solve the same problem. It is shown that the proposed distributed algorithm converges to a global minimizer provided that the digraph (representing the interaction topology of the agents) is strongly connected. All the updates used in the distributed algorithm rely only on local knowledge.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Neurocomputing - Volume 270, 27 December 2017, Pages 91-100
Journal: Neurocomputing - Volume 270, 27 December 2017, Pages 91-100
نویسندگان
Yun Xu, Gangfeng Yan, Kai Cai, Zhiyun Lin,