Matchpair function to solve linear assignment problem

1. I want to know whether Hungarian algorithm is an exact solution algorithm or a heuristic?

2. 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)?

[Steven Lord]

For more information about the algorithm matchpairs implements, see the reference listed in the References section on the documentation page for the matchpairs function.

[Danish Nasir]

I already read the documentation. But time complexity of Matchpair is not mentioned in the documentation. Matchpair is fast but quality of optimal solution is quite inferior compared to Hungarian.

Answer 1

[Walter Roberson]

The Hungarian Algorithm is an exact solution for linear assignment problems.

https://en.wikipedia.org/wiki/Hungarian_algorithm

I do not know anything about the algorithm used by matchpair() but I do notice that it handles the possibility of rows without matches (such as idle workers), which the Hungarian Algorithm by itself does not handle.