.png){kind=icon}
返回
A distributed message passing algorithm for computing perfect demand matching
.png){kind=icon}
PRE
AI
DOI：10.1016/j.jpdc.2023.04.007.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
In this paper, we consider the perfect demand matching problem (PDM) which combines aspects of the knapsack problem along with the b-matching problem. It is a generalization of the maximum weight matching problem which has been fundamental in the development of theory of computer science and operations research. This problem is NP-hard and there exists a constant c > 0 such that the problem admits no 1 + c-approximation algorithm, unless P=NP. Here, we investigate the performance of a distributed message passing algorithm called Max-sum belief propagation for computing the problem of finding the optimal perfect demand matching. As the main result, we demonstrate the rigorous theoretical analysis of the Max-sum BP algorithm for PDM, and establish that within pseudo-polynomial-time, our algorithm could converge to the optimal solution of PDM, provided that the optimal solution of its LP relaxation is unique and integral. Different from the techniques used in previous literature, our analysis is based on primal-dual complementary slackness conditions, and thus the number of iterations of the algorithm is independent of the structure of the given graph. Moreover, to the best of our knowledge, this is one of a very few instances where BP algorithm is proved correct for NP-hard problems.(c) 2023 Elsevier Inc. All rights reserved.
Keyword:
Distributed algorithm
Message passing
Belief propagation
Perfect demand matching
Linear programming dual
期刊
IF:
4
论文数:
3.8K
被引数:
4.8K
机构
引用论文
APIXABAN AND RIVAROXABAN VERSUS WARFARIN AS ATRIAL FIBRILLATION OR VENOUS THROMBOEMBOLISM TREATMENT IN SEVERELY OBESE PATIENTS: A MULTICENTER RETROSPECTIVE ANALYSIS阿哌沙班和利伐沙班与华法林在房颤或静脉血栓栓塞症治疗中严重肥胖患者的应用：一项多中心回顾性分析
PREAI
分享收藏Three-dimensional nanofabrication via ultrafast laser patterning and kinetically regulated material assembly通过超快激光图案化和动力学调节的材料组装进行三维纳米加工.png)
Science
OAAI
ScienceIF0
OAAI分享收藏
分享收藏
查看更多内容