A shortest augmenting path algorithm for dense and sparse linear assignment problems¶
Authors: R. Jonker, A. Volgenant
Published: 1987 (Journal Paper)
Source: Computing
Algorithm: Jonker-Volgenant Algorithm
DOI: 10.1007/BF02278710
Summary¶
Abstract¶
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.