Convergence and correctness of belief propagation for weighted min-max flow

DOI10.1016/j.dam.2021.12.025zbMATH Open1548.90418MaRDI QIDQ6558678

Zan-Bo Zhang, Guowei Dai, Xiaoyan Zhang, Longkun Guo, Gregory Gutin

Publication date: 20 June 2024

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

zbMATH Keywords

belief propagationmessage-passing algorithmmin-max flowmin-max BP algorithm

Mathematics Subject Classification ID

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

Cites Work

• Clustering by Passing Messages Between Data Points
• On the equivalence of the maximum balanced flow problem and the weighted minimax flow problem
• A general Hungarian method for the algebraic transportation problem
• Convergence and correctness of belief propagation for the Chinese postman problem
• Belief Propagation for Min-Cost Network Flow: Convergence and Correctness
• Belief Propagation for Weighted b-Matchings on Arbitrary Graphs and its Relation to Linear Programs with Integer Solutions
• Constructing Free-Energy Approximations and Generalized Belief Propagation Algorithms
• Max-Product for Maximum Weight Matching: Convergence, Correctness, and LP Duality
• Minimizing maximum flows in linear graphs
• FINDING THE WEIGHTED MINIMAX FLOW IN A POLYNOMIAL TIME
• WEIGHTED MINIMAX REAL-VALUED FLOWS
• An Optimal Algorithm for Weighted Minimax Flow Centers on Trees
• 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
• 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
• On the solution-space geometry of random constraint satisfaction problems

This page was built for publication: Convergence and correctness of belief propagation for weighted min-max flow