MATLAB: Matchpairs function in r2019a

linear assignment problemMATLAB

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

Best Answer

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.
Related Question