A distributed message passing algorithm for the capacitated directed Chinese postman problem.

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) }. [Display omitted] • 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. [ABSTRACT FROM AUTHOR]