Solving large-scale assignment problems by Kuhn-Munkres algorithm

Abstract

Kuhn-Munkres algorithm is one of the most popular polynomial time algorithms for solving classical assignment problem. The assignment problem is to find a n a ssignment o f t he j obs t o t he w orkers that has minimum cost, given a cost matrix X R mn , where the element in the i-th row and j-th column represents the cost of assigning the i-th job to the j-th worker. the time complexity of Kuhn-Munkres algorithm is O(mn 2 ), which brings prohibitive computational burden on large scale matrices, limiting the further usage of these methods in real applications. Motivated by this observation, a series of acceleration skills and parallel techniques have been studied on special structure. In this paper, we improve the original Kuhn-Munkres algorithm by utilizing the sparsity structure of the cost matrix, and propose two algorithms, sparsity based KM(sKM) and parallel KM(pKM). Furthermore, numerical experiments are given to show the efficiency of our algorithm. We empirically evaluate the proposed algorithm sKM) and (pKM) on random generated largescale datasets. Results have shown that sKM) greatly improves the computational performance. At the same time, (pKM) provides a parallel way to solve assignment problem with considerable accuracy loss.