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

Version 1.14.0.0 (4,35 KB) von Yi Cao
A Matlab implementation of the Jonker-Volgenant algorithm solving LAPs.
4.9
(21)
5,5K Downloads
Aktualisiert 11. Apr 2013

Lizenz anzeigen

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.

Zitieren als

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. Abgerufen.

Kompatibilität der MATLAB-Version
Erstellt mit R2010a
Kompatibel mit allen Versionen
Plattform-Kompatibilität
Windows macOS Linux
Kategorien
Mehr zu Construction finden Sie in Help Center und MATLAB Answers

Community Treasure Hunt

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

Start Hunting!

Version Veröffentlicht Versionshinweise
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