Primal-dual algrorithms for the assignment problem

AbstractPrimal-dual algorithms for the min-sum linear assignment problem are summarized. Procedures obtained by combining the Hungarian and Shortest Augmenting Path methods for complete and sparse cost matrices are presented. A new algorithm is proposed for the complete case, which transforms the complete cost matrix into a sparse one, solves the sparse problem and checks the optimality of the solution found with respect to the original problem. Extensive computational results on different classes of randomly-generated test problems are presented both for complete and sparse cost matrices