Code covered by the BSD License

### Highlights fromMunkres Assignment Algorithm

4.2

4.2 | 5 ratings Rate this file 44 Downloads (last 30 days) File Size: 2.69 KB File ID: #20328

# Munkres Assignment Algorithm

by Yi Cao

17 Jun 2008 (Updated 27 Jun 2008)

An efficient implementation of the Munkres algorithm for the assignment problem.

File Information
Description

Munkres algorithm (also known as Hungarian algorithm) is an efficient algorithm to solve the assignment problem in polynomial-time. The algorithm has many applications in combinatorial optimization, for example in Traveling Salesman problem.

There are a few submissions in the File Exchange for the Munkres algorithm. However, most of them are not efficient. Therefore, I decided to develop my own code. By comparing with existing programms, this code is about two to 5 times faster. For instance, for a 400 x 400 random example, this code can solve it in 4 to 6 seconds, whilst other programs have to take about 17 to 35 seconds.

Acknowledgements

Assignprob.Zip, Functions For The Rectangular Assignment Problem, and Hungarian Algorithm inspired this file.

MATLAB release MATLAB 7.6 (R2008a)
Tags for This File
Everyone's Tags
Tags I've Applied
09 Oct 2012

there is no solution for the following matrix?
1 4 Inf
Inf Inf 5
Inf Inf 7
How do I modify such that it provides the
assignment =
1 0 0
0 0 1
0 0 0

08 Oct 2012

I have a 15x51 matrix on which this algorithm fails. the JV handles it.

can I send you the matrix

20 Apr 2012

This is much faster than the version 1.0. Thanks!

30 Jan 2012

Hi,

i have also a cost matrix which returns zero assignments while the Hungarian (http://www.mathworks.com/matlabcentral/fileexchange/11609-hungarian-algorithm) algorithm works fine...

01 Oct 2011
29 Sep 2011

Hi

I have a cost matrix for which this script does not seem to work. It seems to make random assignments where the candidate has maximum costs (inf). Could you help?

12 Oct 2010

but i have a question

is the time complexity of your algorithm on the order of n^3 or n^4?

30 Jun 2010

Yi,

There was a problem with my data, that did not occur in any of my other cases.

Thanks again!

Kevin

24 Jun 2010

Kevin,

Thanks for comments. I have looked at your problem. Actually, the problem does not have a valid solution. The code you linked does not provide a valid solution either. If you check the solution, you will find many zeros, which means no valid assignment can be done for these positions.

HTH
Yi

22 Jun 2010

This is extremely fast compared to the other Hungarian algorithms I've seen posted here.

I have successfully used this many times to optimally connect line segments such that the total cost is minimized.

However, I did find a case in which the assignment matrix does not return any matches, but some of the slower algorithms do.

For example, i got results using Markus Buehren's algorithm at
http://www.mathworks.com/matlabcentral/fileexchange/6543

My distance matrix is found here:
http://www.bigfoot.com/~Kevin.Crosby/public/distance.mat

Do you have a quick fix for this?

Thanks!

03 Mar 2010

Truly excellent. It has everything you could ask of a Matlab program: good structure, excellent comments, simplicity, flow and efficiency. Thank you for sharing.

05 Apr 2009