File Exchange

## Munkres Assignment Algorithm

version 1.0 (2.69 KB) by

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

4.16667
7 Ratings

Updated

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.

yechen tang

umang vaishnav

### umang vaishnav (view profile)

Hello, Yi Cao

Thank you for uploading Munkres algorithm. However, as this assignment is only for Minimum assignment, If i want to assign for Maximum assignment then what changes needs to be done in your code?

Suppose matrix [2, 4, 6;8, 6, 10;12, 14, 20]

Min. Assignment is 24. But If I want to Max. assignment then?

mathu Mari

### mathu Mari (view profile)

Is it possible for you explain the commands how it is perform here? Need to understand whole program. I m new to matlab and programming.

Paul Quinn

### Paul Quinn (view profile)

Bug: fails for input row vector [5 4 3 1].
Fix(?): validCol = any(validMat, 1); (dimension for any is not specified in the original code for validCol.)

Matteo

### Matteo (view profile)

Hi people,
I a question about the hungarian algorithm. this algorithm is optimal algorithm for the assignment problem, and the time complexity is O(n^3), right?
But , if the input is the multidimensional matrix, it's possible to use the hungarian algorithm? how does it change the algorithm and the time complexity ?
thanks

Markus Buehren

David Manegold

### David Manegold (view profile)

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

David Manegold

### David Manegold (view profile)

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

can I send you the matrix

Arun Kumar Chithanar

### Arun Kumar Chithanar (view profile)

This is much faster than the version 1.0. Thanks!

Max

### Max (view profile)

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

Christoph

Christoph

### Christoph (view profile)

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?

Jiangmin zhang

### Jiangmin zhang (view profile)

but i have a question

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

Kevin Crosby

### Kevin Crosby (view profile)

Yi,

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

Thanks again!

Kevin

Yi Cao

### Yi Cao (view profile)

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

Kevin Crosby

### Kevin Crosby (view profile)

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!

Zacharias Voulgaris

### Zacharias Voulgaris (view profile)

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

V. Poor