.png){kind=icon}
Return
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}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
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.
Keywords:
Distributed algorithm
Message passing
Belief propagation
Perfect demand matching
Linear programming dual
Journal
IF:
4
Papers:
3.8K
Citations:
4.8K
Organization
Cited Papers
Three-dimensional nanofabrication via ultrafast laser patterning and kinetically regulated material assembly.png)
Science
OAAI
ScienceIF0
OAAIShareSave
ShareSaveShareSaveShareSave
View more