.png){kind=icon}
Return
A distributed message passing algorithm for the capacitated directed Chinese postman problem
.png){kind=icon}
PRE
AI
DOI：10.1016/j.compeleceng.2022.107755.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
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 is an element of E(G)}.
Keywords:
Distributed algorithm
Message passing
Belief propagation
Capacitated directed Chinese postman problem
Combinatorial optimization
Journal
C
IF:
4.9
Papers:
6.7K
Citations:
1.3W
Organization
Cited Papers
Three-dimensional nanofabrication via ultrafast laser patterning and kinetically regulated material assembly.png)
Science
OAAI
ScienceIF0
OAAIShareSaveShareSave
ShareSaveShareSave
View more