A new implementation of an algorithm for the optimal assignment problem: An improved version of Munkres' algorithm |
| |
| Authors: | Jin Kue Wong |
| |
| Institution: | (1) Department of Systems & Information Science, Vanderbilt University, 37235 Nashville, Tennessee, U.S.A.;(2) Present address: Department of Computer Science, University of Ottawa, Kin 6N5 Ottawa, Ontario, Canada |
| |
| Abstract: | Existing implementations of Munkres' algorithm for the optimal assignment problem are shown to requireO(n
4) time in the worstn×n case. A new implementation is presented which runs in worst-case timeO(n
3) and compares favorably in performance with the algorithm of Edmonds and Karp for this problem.The results of this paper were obtained by the author while at the Department of Computer Science, Cornell University. This work was supported in part by a Vanderbilt University Research Council Grant. |
| |
| Keywords: | Optimal assignment problem worst-case time analysis of algorithms |
| 本文献已被 SpringerLink 等数据库收录！ |
|
