Solving the Many to Many assignment problem by improving the Kuhn-Munkres algorithm with backtracking
详细信息 查看全文
- 作者：Haibin Zhub ; Dongning Liua ; liudn@gdut.edu.cn" class="auth_mail" title="E-mail the corresponding author ; Siqin Zhanga ; Yu Zhuc ; Luyao Tengd ; Shaohua Tenga
- 关键词：Assignment problem ; Many to Many assignment ; Kuhn&ndash ; Munkres algorithm ; Hungarian method
- 刊名：Theoretical Computer Science
- 出版年：2016
- 出版时间：7 March 2016
- 年：2016
- 卷：618
- 期：Complete
- 页码：30-41
- 全文大小：770 K
文摘
- •
It improves the K–M algorithm to solve the M–M assignment problem.
- •
The improved algorithm (KMB) introduces backtracking.
- •
The KMB algorithm is valid and the worst time complexity is O((∑La[i])3).
- •
It provides the necessary and sufficient conditions for the solution.
- •
It illustrates the validity and efficiency of the KMB algorithm through simulations.