File Exchange

image thumbnail

Faster Jonker-Volgenant Assignment Algorithm

version 1.1.0.0 (4.76 KB) by Eric Trautmann
This is a modification made to Yi Cao's original JV algorithm code to improve speed.

2 Downloads

Updated 03 Jul 2012

View License

This updated version performs the JV algorithm for a standard assignment problem for only valid entries in the cost matrix.

The modification removes rows and columns of the matrix where all values are inf, which is useful for applications where it is necessary to mask off certain assignments, such as in the k-best assignment algorithm (Murty algorithm).

The improvement in the runtime is dependent upon how many rows/cols are masked, but can be as 7-20x for many cases.

Yi Cao agreed to let me post this update, and the majority of the code is his.

Cite As

Eric Trautmann (2019). Faster Jonker-Volgenant Assignment Algorithm (https://www.mathworks.com/matlabcentral/fileexchange/30838-faster-jonker-volgenant-assignment-algorithm), MATLAB Central File Exchange. Retrieved .

Comments and Ratings (3)

Hüseyin

This code works perfectly! It only returns the full assignment matrix with logical values 1/0.
To get same result as in Yi Cao's Jonker-Volgenant algorithm, use this code:

[a,b]=lapjv_fast(Ain,1e-10); % I used that resolution 1e-10
A=mod(find(a(:,:)'==1),length(a))'; % for each row find index of logical '1'
A(A==0)=length(A); % We used mod function - so replace 0 by the length of row

OR

change the function lapjv_fast.m as:

function [assignment,assignmentMat,cost] = lapjv_fast(costMat,resolution)
...
line 657:
assignmentMat = false(rdim,cdim);
for rowind=1:rdim
assignmentMat(rowind,rowsol(rowind)) = true;
end
assignment=rowsol;

- Results are identical with Yi Cao's algorithm.
- Runtime behavior:
n=1.000 -> speedup: 108 sec vs. 0.0681 sec
n=2.000 -> speedup: 246 sec vs. 0.4310 sec
n=3.000 -> speedup: 565 sec vs. 0.9342 sec
n=4000 -> speedup 2179 sec vs 1.1076 sec
n=5000 -> speedup 2485 sec vs 1.3242 sec
...
n=10000 -> pseedup 9063 sec vs 5.4112 sec

All with same result !

hi

i ran this code on a 7036x3597 matrix and there seem to be a bug in the section where you pad the output matrix to look like munkres.

for rowind=1:size(dMat,1)
assignment_small(rowind,rowsol(rowind))=1;
end

the error i got was the code trying to access rowsol(3598), when rowsol only has 3597 rows. It worked fine when i transposed my input data (so that there are more columns than rows).

Thanks.

Updates

1.1.0.0

Thanks to Mark Tincknell for submitting an update to generalize this for arbitrary rectangular matrices.

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