Correctness And Convergence Of Belief Propagation For The Chinese Postman Problem

Belief Propagation (BP), a distributed, message-passing algorithm, has been widely used in different disciplines including information theory, artificial intel-ligence, statistics and combinatorial optimization problems in graphical models such as Bayesian networks and Markov random fields. Despite BP has a great success in many application fields and many progress about BP has been made,the rigorous analysis about the correctness and convergence of BP are known in only a few cases for arbitrary graph. As a major breakthrough, it has been established that BP converges to the maximum weighted matching (Bayati et al.(2008), Sanghavi et al. (2011)) and the min-cost flow problem (Gamarnik et al.(2012)) in general graphs provided some assumptions, respectively.With the goal of identifying the broadest class of optimization problems solvable using the simple BP algorithm directly, we will investigate the correct-ness and convergence of BP for determining the optimal solutions of the Chinese postman problem in both undirected and directed graphs. The undirected Chi-nese postman problem (LUCPP) can be formulated as an integer programming containing the constraint with module 2 congruence. It is in general more com-plicated than the directed Chinese postman problem (DCPP), where finding the optimal solution of DCPP, i.e., determining a minimum cost Eulerian directed graph, can be achieved by solving a minimum cost flow problem. As a main re-sult of this paper, we prove that BP converges to the optimal solution of UCPP within O(n) iterations where n represents the number of vertices, provided that the optimal solution is unique. For the directed case, we consider the direct-ed Chinese postman problem with capacity (DCPP) which can be considered as a variant of capacity arc routing problem and show that BP also converges to its optimal solution after O(n) iterations, as long as its corresponding lin-ear programming (LP) relaxation has the unique optimal solution. Our proof techniques and iterative times based on complementary slackness conditions of the LP relaxation and its dual are different from those given by Gamarnik et al.(2012) for the min-cost flow problem. In the end, we state the asynchronous BP algorithm and show that it has the results as good as the synchronous BP algo-rithm for the Chinese postman problem in both undirected and directed graphs.