A shortest augmenting path algorithm for dense and sparse linear assignment problems

• DOI: 10.1007/bf02278710
• Publication Date: 2005-12-09T14:43:25Z
• Authors: R. Jonker; A. Volgenant
• Keywords: 0202 electrical engineering, electronic engineering, information engineering; 02 engineering and technology

We develop a shortest augmenting path algorithm for the linear assignment problem. It contains new initialization routines and a special implementation of Dijkstra's shortest path method. For both dense and sparse problems computational experiments show this algorithm to be uniformly faster than the best algorithms from the literature. A Pascal implementation is presented.