A distributed message passing algorithm for the capacitated directed Chinese postman problem. (April 2022)

• Record Type: Journal Article
• Authors: Dai, Guowei; Sun, Yuefang; Zhang, Xiaoyan; Zhao, Yan
• Is Part Of: Computers & electrical engineering. Volume 99(2022)
• Publication Date: 2022-04
• Subjects: Distributed algorithm -- Message passing -- Belief propagation -- Capacitated directed Chinese postman problem -- Combinatorial optimization; Computer engineering -- Periodicals; Electrical engineering -- Periodicals; Electrical engineering -- Data processing -- Periodicals; Ordinateurs -- Conception et construction -- Périodiques; Électrotechnique -- Périodiques; Électrotechnique -- Informatique -- Périodiques; Computer engineering; Electrical engineering; Electrical engineering -- Data processing; Periodicals; Electronic journals; 621.302854
• DOI: 10.1016/j.compeleceng.2022.107755
• Languages: English
• ISSNs: 0045-7906

Abstract

Abstract: Message passing is a class of extremely powerful distributed iterative algorithms based on probabilistic graphic model, in which little computation performed per iteration on minimal data structure. As a prototypical message-passing algorithm, belief propagation (BP) algorithm has wide applications in various fields of coding theory, machine learning and combinatorial optimization. Due to its distributed and iterative nature, BP algorithm can run effectively and fast on large data networks. In this paper, we study the behavior of Min-Sum BP algorithm for the capacitated directed Chinese postman problem ( CDCP ). We derive the iterative process of message passing for solving CDCP . As the main result, for any weighted digraph G of size n, if the weight on each edge is nonnegative integral, then our algorithm converges to the optimal solution of CDCP after O ( w ∗ n 2 ) iterations, provided that CDCP has a unique optimal solution, where w ∗ = max { w e : e ∈ E ( G ) } . Graphical abstract: Highlights: Message passing is a class of extremely powerful distributed iterative algorithms based on probabilistic graphic model. Due to its distributed and iterative nature, belief propagation (BP) algorithm can run effectively and fast on large data networks. BP-based algorithms can also run fast on a large data network in synchronous circumstances. Min-Sum BP algorithm could converge to the optimal solution of the capacitated directed Chinese postman problem after O ( w m a x n 2 ) iterations.