The Hungarian method is a combinatorial optimization algorithm that solves the assignment problem in polynomial time and which anticipated later primal-dual methods. It was developed and published in 1955 by Harold Kuhn, who gave 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.
Contents
- Simple explanation of the assignment problem
- Setting
- The algorithm in terms of bipartite graphs
- Matrix interpretation
- References
James Munkres reviewed the algorithm in 1957 and observed that it is (strongly) polynomial. Since then the algorithm has been known also as the Kuhn–Munkres algorithm or Munkres assignment algorithm. The time complexity of the original algorithm was
Simple explanation of the assignment problem
In this simple example there are three workers: Armond, Francine, and Herbert. One of them has to clean the bathroom, another sweep the floors, and the third wash the windows, but they each demand different pay for the various tasks. The problem is to find the lowest-cost way to assign the jobs. 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 $6, achieved by having Armond clean the bathroom, Francine sweep the floors, and Herbert wash the windows.
Setting
We are given a nonnegative 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. We have to find an assignment of the jobs to the workers that has minimum cost. If the goal is to find the assignment that yields the maximum cost, the problem can be altered to fit the setting by replacing each cost with the maximum cost subtracted by the cost.
The algorithm is easier to describe if we formulate the problem using a bipartite graph. We have a complete bipartite graph
Let us call a function
The algorithm in terms of bipartite graphs
During the algorithm we maintain a potential y and an orientation of
In a general step, let
If
If
We repeat these steps until M is a perfect matching, in which case it gives a minimum cost assignment. The running time of this version of the method is
Matrix interpretation
Given
First the problem is written in the form of a matrix as given below
where a, b, c and d are the workers who have to perform tasks 1, 2, 3 and 4. a1, a2, a3, a4 denote the penalties incurred when worker "a" does task 1, 2, 3, 4 respectively. The same holds true for the other symbols as well. The matrix is square, so each worker can perform only one task.
Step 1
Then we perform row operations on the matrix. To do this, the lowest of all ai (i belonging to 1-4) is taken and is subtracted from each element in that row. This will lead to at least one zero in that row (We get multiple zeros when there are two equal elements which also happen to be the lowest in that row). This procedure is repeated for all rows. We now have a matrix with at least one zero per row. Now we try to assign tasks to agents such that each agent is doing only one task and the penalty incurred in each case is zero. This is illustrated below.
The zeros that are indicated as 0' are the assigned tasks.
Step 2
Sometimes it may turn out that the matrix at this stage cannot be used for assigning, as is the case in for the matrix below.
In the above case, no assignment can be made. Note that task 1 is done efficiently by both agent a and c. Both can't be assigned the same task. Also note that no one does task 3 efficiently. To overcome this, we repeat the above procedure for all columns (i.e. the minimum element in each column is subtracted from all the elements in that column) and then check if an assignment is possible.
In most situations this will give the result, but if it is still not possible then we need to keep going.
Step 3
All zeros in the matrix must be covered by marking as few rows and/or columns as possible. The following procedure is one way to accomplish this:
First, assign as many tasks as possible.
Alternatively, the 0 in row 3 may be assigned, causing the 0 in row 1 to be crossed instead.
Now to the drawing part.
Now draw lines through all marked columns and unmarked rows.
The aforementioned detailed description is just one way to draw the minimum number of lines to cover all the 0s. Other methods work as well.
Step 4
From the elements that are left, find the lowest value. Subtract this from every unmarked element and add it to every element covered by two lines.
Repeat steps 3–4 until an assignment is possible; this is when the minimum number of lines used to cover all the 0s is equal to max(number of people, number of assignments), assuming dummy variables (usually the max cost) are used to fill in when the number of people is greater than the number of assignments.
Basically you find the second minimum cost among the remaining choices. The procedure is repeated until you are able to distinguish among the workers in terms of least cost.