image thumbnail

LAPJV - Jonker-Volgenant Algorithm for Linear Assignment Problem V3.0

version 1.14.0.0 (4.35 KB) by Yi Cao
A Matlab implementation of the Jonker-Volgenant algorithm solving LAPs.

5.2K Downloads

Updated 11 Apr 2013

View License

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.
v3.0 fixes a bug introduced since v2.0.
Reference:
R. Jonker and A. Volgenant, "A shortest augmenting path algorithm for dense and spare linear assignment problems", Computing, Vol. 38, pp. 325-340, 1987.

Cite As

Yi Cao (2021). LAPJV - Jonker-Volgenant Algorithm for Linear Assignment Problem V3.0 (https://www.mathworks.com/matlabcentral/fileexchange/26836-lapjv-jonker-volgenant-algorithm-for-linear-assignment-problem-v3-0), MATLAB Central File Exchange. Retrieved .

MATLAB Release Compatibility
Created with R2010a
Compatible with any release
Platform Compatibility
Windows macOS Linux

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!