matchpairs function in r2019a

I used matchpairs function to solve linear assignment problem but was wondering which algorithm it implemented and the time complexity. Is it Hungarian?

Thank you

Answer 1

[Christine Tobler]

The algorithm solves the same problem as the Hungarian algorithm, but it's not the same algorithm. The Hungarian algorithm has complexity O(N^4), while the algorithm used here has complexity O(N^3*log(N)) for dense matrices, and O(nnz*N*log(N)) for sparse matrices.

These are worst-case complexities, for many matrices the performance will be better, as simple cases are treated in a preprocessing step.

If you type 'edit matchpairs', there is a reference to a paper describing the algorithm used in that file.

[Lingyao Meng]

Thanks a lot

[Steven Lord]

The paper is also listed in the References section of the documentation page for matchpairs. That way you avoid the chance of accidentally modifying matchpairs.m.

[Mingxing]

Thanks for your answer. I checked the algorithm file of 'matchpairs' and I found that there is a 'matlab.internal.graph.perfectMatching' function to perform matching (no further explainations). I am wondering what exactly it is.

And I also checked the reference paper, the paper actually gave several algorithms.