.png){kind=icon}
返回
Fast centralized integer resource allocation algorithm and its distributed extension over digraphs
.png){kind=icon}
PRE
AI
DOI：10.1016/j.neucom.2017.03.089.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
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(n logn +/- n log D) when the resource constraints of individual agents are [0, D], which outperforms the best known multiphase algorithm with O(n log n logD). 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. (C) 2017 Elsevier B.V. All rights reserved.
Keyword:
Min-heap
Resource allocation
Distributed algorithm
Consensus
Strongly connected digraph
AI总结
对已上传原文的论文进行重点信息的提取，主要内容包括：简要概述、研究摘要、背景介绍、关键亮点、图文解析、展望与总结。
期刊
IF:
6.5
论文数:
2.5W
被引数:
6.5W
机构
引用论文
.png){kind=icon}
查看更多内容