A new algorithm for the assignment problem

Mathematical Programming 21 (1981) 152-171 North-Holland Publishing Company A NEW ALGORITHM FOR THE ASSIGNMENT PROBLEM* Dimitri P. BERTSEKAS Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology, Cambridge, MA 02139, U.S.A. Received 15 August 1979 Revised manuscript received 6 October 1980 We propose a new algorithm for the classical assignment problem. The algorithm resembles in some ways the Hungarian method but differs substantially in other respects. The average computational complexity of an efficient implementation of the algorithm seems

to be considerably better than the one of the Hungarian method. In a large number of randomly generated problems the algorithm has consistently outperformed an efficiently coded version of the Hungarian method by a broad margin. The factor of improvement increases with the problem dimension N and reaches an order of magnitude for N equal to several hundreds. Key words: Assignment Problems, Network Flows, Hungarian Method, Computational Complexity. 1. Introduction The assignment problem was among the first linear programming problems to be studied extensively. It arises often in practice and it is a fundamental problem in network flow theory since a number of other problems, such as the shortest path, weighted matching, transportation and minimum cost flow problems, can be reduced to it [l, p. 186-187]. It is characteristic in this respect that the first specialized method for the assignment problem, namely Kuhn's Hungarian method [2], was subsequently extended for solution of much more general network flow problems. Furthermore, some of its main ideas were instrumental in the development of more general methods such as the out-of-kilter and nonbipartite matching methods. This suggests that the assignment problem is not only important in itself, but is also suitable for development of new com- putational ideas in network flow theory. It is for this reason that we restrict attention to the assignment problem even though the ideas of this paper have extensions to more general problems. It seems that the currently most popular solution methods for the assignment problem are specialized forms of the simplex method [3-5] and versions of Kuhn's Hungarian method [6--8]. There has been some controversy regarding the relative merits of simplex codes and primal-dual (i.e. Hungarian) codes ]6, 9]. A recent computational study [7] finds simplex and primal-dual codes roughly comparable, while another study [8] reports that a primal-dual code based on the * Work supported by Grant NSF ENG-7906332. 152 D.P. Bertsekas/ Assignment problem 153 work of Edmonds and Karp [10] outperforms simplex-like algorithms by a considerable margin. The development of specialized codes for the assignment problem using sophisticated programming techniques is an active research area so it is difficult to assess the current state of the art. The computational complexity of many of the existing codes is unknown and in fact some of these codes [3, 6] are proprietary. It is known that the complexity of the Hungarian method for full dense, all integer, N ×...

Website: web.eecs.umich.edu | Filesize: -
No of Page(s): 20
Download A new algorithm for the assignment problem - Visit Web.eecs.umich ....pdf