matchpairs function in r2019a
17 views (last 30 days)
Show older comments
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
0 Comments
Accepted Answer
Christine Tobler
on 2 May 2019
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.
3 Comments
Steven Lord
on 2 May 2019
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
on 8 Oct 2021
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.
More Answers (0)
See Also
Categories
Find more on Sparse Matrices in Help Center and File Exchange
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!