Physicist's view on the unbalanced k-cardinality assignment problem

The k-cardinality unbalanced assignment problem asks for assigning k "agents" to k "tasks" on a one-to-one basis, while minimizing the total cost associated with the assignment, with the total number of agents N and the total number of tasks M possibly different and larger than k. While many exact algorithms have been proposed to find such an optimal assignment, these methods are computationally prohibitive when the problem is large. We propose an approach to solving the k-cardinality assignment problem using techniques adapted from statistical physics. This paper provides a full description of this formalism, including all the proofs of its main claims. We derive a strongly concave free-energy function that captures the constraints of the k-assignment problem at a finite temperature. We prove that this free energy decreases monotonically as a function of β, the inverse of temperature, to the optimal assignment cost, providing a robust framework for temperature annealing. We also prove that for large enough β values the exact solution to the k-assignment problem can be derived using simple round-off to the nearest integer of the elements of the computed assignment matrix. We show that this framework can be adapted to handle degenerate k-assignment problems. We describe a computer implementation of our framework that is optimized for the GPU parallel architecture, using the library CUDA. This implementation is found to be as efficient as state-of-the-art implementations of parallel Hungarian algorithms on generic assignment problems, and orders of magnitude faster than those algorithms for pathological assignment cases.