It was developed and published in 1955 by Harold Kuhn, who gave it the name "Hungarian method" because the algorithm was largely based on the earlier works of two Hungarian mathematicians, Dénes Kőnig and Jenő Egerváry.
[1][2] However, in 2006 it was discovered that Carl Gustav Jacobi had solved the assignment problem in the 19th century, and the solution had been published posthumously in 1890 in Latin.
[3] James Munkres reviewed the algorithm in 1957 and observed that it is (strongly) polynomial.
, however Edmonds and Karp, and independently Tomizawa, noticed that it can be modified to achieve an
[5][6] Ford and Fulkerson extended the method to general maximum flow problems in form of the Ford–Fulkerson algorithm.
In this simple example, there are three workers: Alice, Bob and Carol.
One of them has to clean the bathroom, another sweep the floors and the third washes the windows, but they each demand different pay for the various tasks.
The problem can be represented in a matrix of the costs of the workers doing the jobs.
For example: The Hungarian method, when applied to the above table, would give the minimum cost: this is $15, achieved by having Alice clean the bathroom, Carol sweep the floors, and Bob wash the windows.
This can be confirmed using brute force: In the matrix formulation, we are given an n×n matrix, where the element in the i-th row and j-th column represents the cost of assigning the j-th job to the i-th worker.
If the goal is to find the assignment that yields the maximum cost, the problem can be solved by negating the cost matrix C. The algorithm can equivalently be described by formulating the problem using a bipartite graph.
must exist whenever the matching is not yet of maximum possible size (see the following section); it is positive because there are no tight edges between
We orient the new edges from S to T. By the definition of Δ the set Z of vertices reachable from
We repeat these steps until M is a perfect matching, in which case it gives a minimum cost assignment.
It suffices to show that at least one of the following holds at every step: If M is of maximum possible size, we are of course finished.
and this reasoning process iterated (formally, using induction on the number of loose edges) until either an augmenting path in
is decreased by Δ, leaving the total potential of the edge unchanged, or
After adjusting the potentials in the way described in the previous section, there is now a tight edge from
For convenience of implementation, the code below adds an additional worker
The implementation from the previous section is rewritten below in such a way as to emphasize this connection; it can be checked that the potentials
allowed job, worker pairs), it is possible to optimize this algorithm to run in
This variant of the algorithm follows the formulation given by Flood,[10] and later described more explicitly by Munkres, who proved it runs in
[4] Instead of keeping track of the potentials of the vertices, the algorithm operates only on a matrix: where
Changing the potentials corresponds to adding or subtracting from rows or columns of this matrix.
The problem is equivalent to assigning each worker a unique task such that the total penalty is minimized.
As such, a naive greedy algorithm can attempt to assign all workers a task with a penalty of zero.
We could end with another assignment if we choose another ordering of the rows and columns.
The aforementioned detailed description is just one way to draw the minimum number of lines to cover all the 0s.
If following this specific version of the algorithm, the starred zeros form the minimum assignment.
Thus, when n lines are required, minimum cost assignment can be found by looking at only zeroes in the matrix.