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.
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)?
- Both Hungarian and “matchpair” (inbuilt function in MATLAB) can be used to solve linear assignment problem.
- 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).
- 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:
I hope this helps, Thanks!
