Improving the Hungarian assignment algorithm (Q1085073): Difference between revisions

We describe three easily implementable improvements for the Hungarian linear assignment algorithm. Computation times vary from about two to more than three times lower than previously, where the effectiveness increases with problem size. Furthermore, the algorithm is now less sensitive to the range of the cost coefficients. We also show that the Hungarian algorithm is essentially equivalent to assignment algorithms based on shortest augmenting paths.