Belief propagation for unbalanced assignment problem

DOI10.1142/S0217595922500373MaRDI QIDQ6544915zbMATH OpenFDO

Authors Yajing Wang, Dongyue Liang, Weihua Yang

Publication date 28 May 2024

Published in Asia-Pacific Journal of Operational Research (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1142/S0217595922500373

zbMATH Keywords

belief propagation (BP)message-passing algorithmmin-cost network flow problempseudo-polynomial timeunbalanced assignment problem

Mathematics Subject Classification ID

Theory of organizations, manpower planning in operations research (90B70) Discrete location and assignment (90B80) Combinatorial optimization (90C27) Programming involving graphs or networks (90C35) Matching models (91B68)

Recommendations

• Belief propagation: an asymptotically optimal algorithm for the random assignment problem
• Optimality of belief propagation for random assignment problem
• Belief propagation for min-cost network flow: convergence and correctness
• scientific article; zbMATH DE number 6297707
• Smoothed analysis of belief propagation for minimum-cost flow and matching

Cites work

• A modified method for solving the unbalanced assignment problems
• Analysis of the Min-Sum Algorithm for Packing and Covering Problems via Linear Programming
• 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
• Convergence and correctness of belief propagation for the Chinese postman problem
• Finding minimum-cost circulations by canceling negative cycles
• scientific article; zbMATH DE number 3174791 (Why is no real title available?)
• scientific article; zbMATH DE number 3231692 (Why is no real title available?)
• Implementation and Testing of a Primal-Dual Algorithm for the Assignment Problem
• Max-Product for Maximum Weight Matching: Convergence, Correctness, and LP Duality
• Message Passing for Maximum Weight Independent Set
• On the optimality of solutions of the max-product belief-propagation algorithm in arbitrary graphs
• The generalized distributive law

Cited in

(1)

• Separate but equal: equality in belief propagation for single-cycle graphs

This page was built for publication: Belief propagation for unbalanced assignment problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6544915)