Belief Propagation for Unbalanced Assignment Problem

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.