matchpairs function in r2019a

Question

Lingyao Meng 2019-5-2

0
链接

此问题的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/459820-matchpairs-function-in-r2019a

评论： Mingxing 2021-10-8

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 个评论
显示 -2更早的评论隐藏 -2更早的评论

请先登录，再进行评论。

请先登录，再回答此问题。

Answer 1

Christine Tobler 2019-5-2

0
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/459820-matchpairs-function-in-r2019a#answer_373301

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 个评论
显示 1更早的评论隐藏 1更早的评论

Steven Lord 2019-5-2

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 2021-10-8

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.

请先登录，再进行评论。