Matchpair and Hungarian algorithm

I have a cost matrix of size 400x450. I want to minimize it.

a) Is there any inbuilt function for Hungarian alogorithm in Matlab?

b) I want to know whether Hungarian algorithm is an exact solution algorithm or a heuristic?

c) Also MATLAB has inbuilt fucntion Matchpair to solve linear assignment problem. What is the difference between Hungarian and Matchpair ( in terms of Time complexity, approach,exact or heuristic)?

d) What is the size of cost matrix which Hungarian and Matchpair can solve?

Answer 1

[Harsh Mahalwar]

Hi Danish,

I recognize that you’ve divided your question in 4 parts, so I’ll try answering it in 4 parts!

Is there an inbuilt function for Hungarian algorithm in MATLAB?

No, but I was able to find an optimized implementation of Hungarian algorithm on MathWorks File Exchange.

Since it's not from the official MathWorks, proceed at your own risk.

Hungarian Algorithm for Linear Assignment Problems (V2.3) - File Exchange - MATLAB Central (mathworks.com)

Is Hungarian Algorithm an exact solution algorithm or a heuristic-based algorithm?

It’s an exact solution algorithm.

What is the difference between Hungarian and “matchpair” (in terms of Time complexity, approach, exact or heuristic)?

1. Both Hungarian and “matchpair” (inbuilt function in MATLAB) can be used to solve linear assignment problem.
2. The time complexity for Hungarian algorithm is O(n^3), I am not sure which algorithm “matchpair” function in MATLAB uses but after running this function along with the Hungarian algorithm multiple times, I can definitely conclude that its complexity is definitely less than O(n^3).
3. As far as heuristics go, Hungarian algorithm does not use a heuristic. Again, not sure about the ““matchpair”” function in MATLAB.

What is the size of cost matrix which Hungarian and “matchpair” can solve?

The MATLAB implementation Hungarian algorithm can solve a cost matrix of size (2000, 2000) in 36.4 seconds.

Whereas the ““matchpair”” function takes 0.86 seconds for a matrix of same size.

(I am using a 6 core@2.9GHz processor)

Again, you use the following links to learn more about these functions:

Hungarian Algorithm for Linear Assignment Problems (V2.3) - File Exchange - MATLAB Central (mathworks.com)

Solve linear assignment problem - MATLAB “matchpair”s - MathWorks

I hope this helps, Thanks!

[Christine Tobler]

The matchpairs algorithm is not heuristic. For the complexity, I point you to the reference from the documentation page which has some discussion on complexity:

[1] Duff, I.S. and J. Koster. "On Algorithms For Permuting Large Entries to the Diagonal of a Sparse Matrix." SIAM J. Matrix Anal. & Appl. 22(4), 2001. pp 973–996.

(I found a publicly accessible version of this paper by copying the above into scholar.google.com)