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

Versión 1.14.0.0 (4,35 KB) por Yi Cao
A Matlab implementation of the Jonker-Volgenant algorithm solving LAPs.
4.9
(21)
5,4K descargas
Actualizado 11 abr 2013

Ver licencia

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.

Citar como

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

Compatibilidad con la versión de MATLAB
Se creó con R2010a
Compatible con cualquier versión
Compatibilidad con las plataformas
Windows macOS Linux
Categorías
Más información sobre Construction en Help Center y MATLAB Answers.

Community Treasure Hunt

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

Start Hunting!

Versión Publicado Notas de la versión
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