An efficient algorithm for the linear assignment problem

Although numerous exact algorithms have been proposed so far for the linear assignment problem, they are not necessarily satisfactory from the viewpoint of computation time when considered for application to practical large-scale problems. This paper proposes a new algorithm which can reduce the expected computation time needed to find an exact solution for the linear assignment problem by limiting the search space as much as possible within the scope in which no optimal solution is missed. Here, first, an equation is derived to give an upper bound of the search space so as not to miss an optimal solution in the process of finding an alternating path. Next, data structure is described for developing an operation to limit the search space based on this equation and an assignment algorithm is derived. As the results of experiments, the expected computation time of the algorithm O(n2) for preprocessing and 0(nl.6) for the process of finding an assignment of points were found. In addition, it was shown that the algorithm can be applied to large-scale problems since in the planar assignment problem for which an assignment cost function is defined in the plane, the expected computation time is 0(n1.6) including preprocessing.