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.
4.9
(21)
5.5K 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 (2024). 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
Categories
Find more on Construction in Help Center and MATLAB Answers

Community Treasure Hunt

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

Start Hunting!

Version Published Release Notes
1.14.0.0

A bug introduced since v2.0 is fixed
1.12.0.0

A bugg fix
1.11.0.0

Big fix
1.10.0.0

update description
1.9.0.0

Removes a small bug to handle a cost matrix with all inf's.
1.8.0.0

v2.2 removes a small bug to avoid NAN for 1x1 case.
1.7.0.0

option to change cost resolution.
1.6.0.0

V2.0 is faster for problems with a large range of cost values.

1.5.0.0

update the file
1.4.0.0

V1.2 is able to deal with nonsquare cases.
1.3.0.0

Version 1.1 returns dual variables and reduced cost matrix
1.2.0.0

a bug fixed
1.1.0.0

update descriptions
1.0.0.0