Convergence and correctness of belief propagation for the Chinese postman problem

DOI10.1007/s10898-019-00749-2zbMath1433.90131OpenAlexW2914495126WikidataQ128428088 ScholiaQ128428088MaRDI QIDQ2010094

Yanyan Li

Publication date: 3 December 2019

Published in: Journal of Global Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10898-019-00749-2

zbMATH Keywords

convergencemessage-passing algorithmundirected Chinese postman problembelief propagation (BP)directed Chinese postman problemmin-sum algorithm

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Combinatorial optimization (90C27)

Related Items

Unnamed Item, Hierarchical Chinese postman problem with fuzzy travel times

Uses Software

• apcluster
• APCluster

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Clustering by Passing Messages Between Data Points
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Parallelizing simulated annealing algorithms based on high-performance computer
• Correctness of Belief Propagation in Gaussian Graphical Models of Arbitrary Topology
• Belief Propagation for Min-Cost Network Flow: Convergence and Correctness
• Analysis of the Min-Sum Algorithm for Packing and Covering Problems via Linear Programming
• Belief Propagation for Weighted b-Matchings on Arbitrary Graphs and its Relation to Linear Programs with Integer Solutions
• A Spectral Approach to Analysing Belief Propagation for 3-Colouring
• Complete Convergence of Message Passing Algorithms for Some Satisfiability Problems
• Max-Product for Maximum Weight Matching: Convergence, Correctness, and LP Duality
• A rigorous analysis of the cavity equations for the minimum spanning tree
• The generalized distributive law
• Factor graphs and the sum-product algorithm
• The capacity of low-density parity-check codes under message-passing decoding
• On the optimality of solutions of the max-product belief-propagation algorithm in arbitrary graphs
• Matching, Euler tours and the Chinese postman
• Smoothed Analysis of Belief Propagation for Minimum-Cost Flow and Matching
• Message Passing for Maximum Weight Independent Set
• Belief Propagation and LP Relaxation for Weighted Matching in General Graphs
• The Stochastic Properties of Large Battle Models
• On the solution-space geometry of random constraint satisfaction problems