A distributed message passing algorithm for computing perfect demand matching

• Published in: Journal of parallel and distributed computing 2023-09, Vol.179, p.104706, Article 104706
• Main Authors: Dai, Guowei, Chen, Yannan, Mao, Yaping, Xu, Dachuan, Zhang, Xiaoyan, Zhang, Zan-Bo
• Format: Article
• Language: English
• Subjects: Belief propagation; Distributed algorithm; Linear programming dual; Message passing; Perfect demand matching
• ISSN: 0743-7315; 1096-0848
• DOI: 10.1016/j.jpdc.2023.04.007

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 ϵ>0 such that the problem admits no 1+ϵ-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. •The perfect demand matching problem (PDM) is NP-hard and MAXSNP-complete.•Demonstrate the rigorous theoretical analysis of Max-sum belief propagation for PDM.•The algorithm converges to the optimal solution of PDM within pseudo-polynomial time.•Our analysis is based on primal-dual complementary slackness conditions.