The Hungarian Method for the Assignment Problem¶
Authors: Harold W. Kuhn
Published: 1955 (Journal Paper)
Source: Naval Research Logistics Quarterly
Algorithm: Hungarian algorithm
DOI: 10.1002/nav.3800020109
Summary¶
Introduces the Hungarian algorithm for optimally solving the assignment problem in polynomial time, applying results from König and Egerváry to give a combinatorial method that finds a maximum-weight perfect matching in a bipartite graph.
Abstract¶
Assuming that numerical scores are available for the performance of each of n persons on each of n jobs, the "assignment problem" is the quest for an assignment of persons to jobs so that the sum of the n scores so obtained is as large as possible. It is shown that ideas latent in the work of two Hungarian mathematicians may be exploited to yield a new method of solving this problem.
Links¶
Primary
Standard
Tags¶
-
Assignment problem
-
Hungarian algorithm
-
Combinatorial optimization
-
Linear programming
-
Operations research