Matchpair function to solve linear assignment problem

10 ビュー (過去 30 日間)
Danish Nasir
Danish Nasir 2021 年 8 月 16 日
コメント済み: Danish Nasir 2021 年 8 月 16 日
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)?
  2 件のコメント
Steven Lord
Steven Lord 2021 年 8 月 16 日
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
Danish Nasir 2021 年 8 月 16 日
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.

サインインしてコメントする。

採用された回答

Walter Roberson
Walter Roberson 2021 年 8 月 16 日
The Hungarian Algorithm is an exact solution for linear assignment problems.
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.

その他の回答 (0 件)

カテゴリ

Help Center および File ExchangeSparse Matrices についてさらに検索

製品


リリース

R2020a

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Translated by