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

Version 1.14.0.0 (4,35 ko) par Yi Cao
A Matlab implementation of the Jonker-Volgenant algorithm solving LAPs.
4.9
(21)
5,4K téléchargements
Mise à jour 11 avr. 2013

Afficher la licence

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.

Citation pour cette source

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. Récupéré le .

Compatibilité avec les versions de MATLAB
Créé avec R2010a
Compatible avec toutes les versions
Plateformes compatibles
Windows macOS Linux
Catégories
En savoir plus sur Construction dans Help Center et MATLAB Answers

Community Treasure Hunt

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

Start Hunting!

Version Publié le Notes de version
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