A distributed message passing algorithm for computing perfect demand matching
Guowei Dai, Yannan Chen, Yaping Mao, Dachuan Xu, Xiaoyan Zhang, Zan‐Bo Zhang · Journal of Parallel and Distributed Computing · 2023
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.