In graph theory, the Hungarian algorithm is an algorithm on Combinatorial Optimization, which solves instances of the assignment problem in polynomial time. Its first version, known as the Hungarian method, was invented and published by Harold Kuhn in 1955. The Hungarian method was in turn revised by James Munkres in 1957, and ever since it has been widely known as the Hungarian algorithm, or the Munkres' assignment algorithm, or even as the Kuhn-Munkres algorithm.
Theory
The algorithm developped by Kuhn was largerly based on the earlier works of two other Hungarian mathematicians: Konig and Egervary. The great advantage of Kuhn’s method is that it is strongly polynomial. The main idea of the algorithm is that it combines two separate parts in Egervery’s proof (computing a deficient set and revising the current ) into one.
Modelisation
The algorithm requires to modelise an assignment problem in the form of a NxM matrix, known as the cost matrix, in which each elemenent represents the cost of assigning one of the N workers to one of M jobs. By default the algorithm performs minimization on the elements of the matrix, hence in the case of a price-minimization problem, it is sufficient to begin Gaussian elimination to make zeros appear (at least one zero per line and per column). However in the case of a profit-maximization problem, the cost matrix needs to be modified in a way that the minimization of its elements will result to a maximization of the original cost values. In an infinite-cost problem, the initial cost matrix can be re-modelised by subtracting every element of each line from the maximum value of the element that line (or column respectively). In a finite-cost problem, the all elements are subtracted from the maximum value of the whole matrix.
Algorithm [1]
The algorithm works by increasing the number of zeros in the matrix and searching for a set of starred zeros, one in every row and column. Zeros are primed, starred, or neither during the algorithm. If there are insufficent zeros a quick Gaussian elimination adds more. If there are not enough starred zeros, the primed zeros are starred and the starred zeros primed. Primed zeros are zeros in a column without any more zeros, which, because they are in the same row as another zero were not starred.
- Step 0: Create an nxm matrix called the cost matrix in which each element represents the cost of assigning one of n workers to one of m jobs. Rotate the matrix so that there are at least as many rows as columns and let k=min(n,m).
- Step 1: For each row of the matrix, find the smallest element and subtract it from every element in its row. Go to Step 2.
- Step 2: Find a zero (Z) in the resulting matrix. If there is no starred zero in its row or column, star Z. Repeat for each element in the matrix. Go to Step 3.
- Step 3: Cover each column containing a starred zero. If K columns are covered, the starred zeros describe a complete set of unique assignments. In this case, Go to DONE, otherwise, Go to Step 4.
- Step 4: Find a noncovered zero and prime it. If there is no starred zero in the row containing this primed zero, Go to Step 5. Otherwise, cover this row and uncover the column containing the starred zero. Continue in this manner until there are no uncovered zeros left. Save the smallest uncovered value and Go to Step 6.
- Step 5: Construct a series of alternating primed and starred zeros as follows. Let Z0 represent the uncovered primed zero found in Step 4. Let Z1 denote the starred zero in the column of Z0 (if any). Let Z2 denote the primed zero in the row of Z1 (there will always be one). Continue until the series terminates at a primed zero that has no starred zero in its column. Unstar each starred zero of the series, star each primed zero of the series, erase all primes and uncover every line in the matrix. Return to Step 3.
- Step 6: Add the value found in Step 4 to every element of each covered row, and subtract it from every element of each uncovered column. Return to Step 4 without altering any stars, primes, or covered lines.
- DONE: Assignment pairs are indicated by the positions of the starred zeros in the cost matrix. If C(i,j) is a starred zero, then the element associated with row i is assigned to the element associated with column j.
A minimization problem
Given workers and tasks, and an matrix containing the cost of assigning each worker to a task, find the cost minimizing assigment.
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 a does task 1,2,3,4 respectively. Same hold true for the other symbols as well. Note that the matrix is a square matrix[this has to be so since each agent can perform only one task].
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 the other elements 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.
Note-Matrix notation hasnt been used since formatting is not possible with that
0 a2' 0' a4'
b1' b2' b3' 0'
0' c2' c3' c4'
d1' 0' d3' d4'
The zeros that are indicated as 0' are the assigned tasks.
In some cases it may turn out that the above matrix cannot be used for assigning.
0 a2' a3' a4'
b1' b2' b3' 0
0 c2' c3' c4'
d1' 0 d3' d4'
In the above case no assignment can be made. Note that task 1 is done efficiently by both agent a and c. Both cant 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 and then check if an assignment is possible. In most situations this will give the result, but if it is still not possible to assign then the procedure described below must be followed.
Initially assign as many tasks as possible then do the following[assign tasks in rows 2,3 and 4]-
0 a2' a3' a4'
b1' b2' b3' 0'
0' c2' c3' c4'
d1' 0' d3' d4'
Mark all rows having no assignments [row 1]. Then mark all columns having zeros in that row [column 1]. Then mark all rows having assignments in the given column [row 3]. Then mark all columns having assignments in the given rows. Repeat this till a closed loop is obtained.
×
0 a2' a3' a4' ×
b1' b2' b3' 0'
0' c2' c3' c4' ×
d1' 0' d3' d4'
Now draw lines through all marked columns and unmarked rows.
0 a2' a3' a4'
b1' b2' b3' 0'
0' c2' c3' c4'
d1' 0' d3' d4'
Note-Since a vertical line cannot be drawn a horizontal line is used to cut the 1st column.
From the elements that are left, find the lowest value. Subtract this from all elements that are not struck. Add this to elements that are present at the intersection of two lines. Leave other elements unchanged. Now assign the tasks using above rules. Repeat the procedure till an assignment is possible.
External links
[Munkres Algorithm] A Java implementation
[Munkres Algorithm] A description of serial and parallel implementations.