Convergence and Correctness of Max-Product Belief Propagation for Linear Programming

DOI10.1137/15M1042565zbMath1371.90082OpenAlexW2756487400MaRDI QIDQ5361238

Jinwoo Shin, Sejun Park

Publication date: 27 September 2017

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/15m1042565

zbMATH Keywords

linear programmingcombinatorial optimizationbelief propagation

Mathematics Subject Classification ID

Linear programming (90C05) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Uses Software

• GraphLab

Cites Work

• Unnamed Item
• Unnamed Item
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• 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
• Counting Independent Sets Using the Bethe Approximation
• Belief Propagation: An Asymptotically Optimal Algorithm for the Random Assignment Problem
• Modern Coding Theory
• Constructing Free-Energy Approximations and Generalized Belief Propagation Algorithms
• Graphical Models, Exponential Families, and Variational Inference
• Counting without sampling
• Information, Physics, and Computation
• Polynomial algorithms in linear programming
• Linear Programming
• On the optimality of solutions of the max-product belief-propagation algorithm in arbitrary graphs
• Message Passing for Maximum Weight Independent Set
• Belief Propagation and LP Relaxation for Weighted Matching in General Graphs
• A simple algorithm that proves half‐integrality of bidirected network programming

This page was built for publication: Convergence and Correctness of Max-Product Belief Propagation for Linear Programming