An efficient algorithm for the bipartite matching problem (Q1069866)

The minimum cost bipartite matching problem is considered. An approach based on the solution of a sequence of shortest path sub-problems is proposed. The particular structure of the problem and the use of reduced costs make it possible to devise an efficient ''threshold'' algorithm to solve these sub-problems. The computational behaviour of the proposed procedure is analyzed.