LAPJV - Jonker-Volgenant Algorithm for Linear Assignment Problem V2.4 (Scripts) Publisher's description
from Yi Cao
The Jonker-Volgenant algorithm is much faster than the famous Hungarian algorithm for the Linear Assignment Problem (LAP)
The Jonker-Volgenant algorithm is much faster than the famous Hungarian algorithm for the Linear Assignment Problem (LAP). This Matlab implementation is modified from the original C++ code made by Roy Jonker, one of the inventors of the algorithm. It is about 10 times faster than the munkres code (v2.2) of the author. It can solve a 1000 x 1000 problem in about 3 seconds in a normal Intel Centrino processor.
V1.1 returns the dual variables and the reduced cost matrix as well.
V1.2 can deal with nonsquare assignment problems.
V2.0 is faster for problems with a large range of costs.
V2.1 includes an option to change the cost resolution to improve performance for some problems.
v2.2 removes a small bug to avoid NAN for 1x1 case.
v2.3 removes a small bug to handle a cost matrix with all inf's.
v2.4 fixes a bug associated with resolution to address the known problem of the algorithm.
R. Jonker and A. Volgenant, "A shortest augmenting path algorithm for dense and spare linear assignment problems", Computing, Vol. 38, pp. 325-340, 1987.
System Requirements:MATLAB 7.10 (2010a)
Program Release Status: Major Update
Program Install Support: Install and Uninstall