File Exchange

image thumbnail

Munkres Assignment Algorithm

version 1.0.0.0 (2.69 KB) by Yi Cao

Yi Cao (view profile)
An efficient implementation of the Munkres algorithm for the assignment problem.
4.4
9 Ratings

45 Downloads

Updated 27 Jun 2008

View License

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.

Cite As

Yi Cao (2020). Munkres Assignment Algorithm (https://www.mathworks.com/matlabcentral/fileexchange/20328-munkres-assignment-algorithm), MATLAB Central File Exchange. Retrieved .

Comments and Ratings (22)

Victor Fernandes

Victor Fernandes (view profile)

How do I cite your implementation of the algorithm?

yu xianguo

yu xianguo (view profile)

Well, though the bug I previously reported that occures in assignmentsuboptimal1 & assignmentsuboptimal2. The assignmentoptimal function implementation is very very good! Thank you for your great work!

Peyruz Gasimov

Peyruz Gasimov (view profile)

Sandrine Sanchez

Sandrine Sanchez (view profile)

Hello, I am trying to assign projects to students, they are 20 and they have 5 choices of projects for which they gave a list of preference. I am looking for the best algorithm and try to understand how it works, I have no experience in programmation, at all, could someone help me understanding how I am supposed to insert inputs in the algorithm? Is it the right one actually?
Thanks so much for your help.

yechen tang

yechen tang (view profile)

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?

Thank you in Advance.

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

Markus Buehren (view profile)

There is another version of this package here: http://www.mathworks.com/matlabcentral/fileexchange/20652-hungarian-algorithm-for-linear-assignment-problems-v2-3

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 (view profile)

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

V. Poor (view profile)

Updates

1.0.0.0

fix a bug to handle nan elements.

fix a bug
MATLAB Release Compatibility
Created with R2008a
Compatible with any release
Platform Compatibility
Windows macOS Linux