Belief Propagation for Unbalanced Assignment Problem

Yajing Wang (), Dongyue Liang and Weihua Yang ()
Additional contact information
Yajing Wang: Department of Mathematics, Taiyuan University of Technology, Taiyuan 030024, P. R. China
Dongyue Liang: Department of Mathematics, Taiyuan University of Technology, Taiyuan 030024, P. R. China
Weihua Yang: Department of Mathematics, Taiyuan University of Technology, Taiyuan 030024, P. R. China

Asia-Pacific Journal of Operational Research (APJOR), 2023, vol. 40, issue 06, 1-19

Abstract: The unbalanced assignment problem (UAP) aims to distribute a set of jobs to some workers. The cost of the jobs is different when they are distributed to different workers. The goal is: (1) minimizing the total cost of arranging jobs to workers; (2) making the distribution of jobs as even as possible among all the workers. We transform the UAP into a min-cost network flow problem with squared terms, and apply the belief propagation (BP) algorithm to deal with it. We prove that, when the min-cost network flow problem has a unique optimal solution, the BP algorithm converges to the optimal solution within O(βn 𠜀 ) iterations, where n represents the number of vertices of the flow network, 𠜀 is the difference between value of the optimal solution and the second optimal solution and β is the maximum value of the terms of the objective function. Next, we prove that BP converges to the optimal solution in O(β2n2μmlog n) operations, where m represents the number of edges and μ is the tight upper bound of the slope of the terms of the objective function.

Keywords: Belief propagation (BP); message-passing algorithm; unbalanced assignment problem; min-cost network flow problem; pseudo-polynomial time (search for similar items in EconPapers)
Date: 2023
References: Add references at CitEc
Citations:

Downloads: (external link)
http://www.worldscientific.com/doi/abs/10.1142/S0217595922500373
Access to full text is restricted to subscribers

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:wsi:apjorx:v:40:y:2023:i:06:n:s0217595922500373

Ordering information: This journal article can be ordered from

DOI: 10.1142/S0217595922500373

Access Statistics for this article

Asia-Pacific Journal of Operational Research (APJOR) is currently edited by Gongyun Zhao

More articles in Asia-Pacific Journal of Operational Research (APJOR) from World Scientific Publishing Co. Pte. Ltd.
Bibliographic data for series maintained by Tai Tone Lim ().