Code covered by the BSD License  

Highlights from
Faster Jonker-Volgenant Assignment Algorithm

1.0

1.0 | 1 rating Rate this file 6 Downloads (last 30 days) File Size: 4.76 KB File ID: #30838

Faster Jonker-Volgenant Assignment Algorithm

by

 

23 Mar 2011 (Updated )

This is a modification made to Yi Cao's original JV algorithm code to improve speed.

| Watch this File

File Information
Description

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.

Acknowledgements

Lapjv Jonker Volgenant Algorithm For Linear Assignment Problem V3.0 inspired this file.

MATLAB release MATLAB 7.11 (R2010b)
Tags for This File   Please login to tag files.
Please login to add a comment or rating.
Comments and Ratings (2)
10 Jan 2013 Matthew

Junk code. Go to the original: http://www.mathworks.com.au/matlabcentral/fileexchange/26836-lapjv-jonker-volgenant-algorithm-for-linear-assignment-problem-v2-5

08 Dec 2011 yanchuan sim

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
03 Jul 2012

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

Contact us