HUNGARIAN ALGORITHM

(Redirected from Munkres\' assignment algorithm)
The 'Hungarian algorithm' is a combinatorial optimization algorithm which solves assignment problems in polynomial time ($O(n^3)$). The first version, known as the 'Hungarian method', was invented and published by Harold Kuhn in 1955. This was revised by James Munkres in 1957, and has been known since as the 'Hungarian algorithm', the 'Munkres assignment algorithm', or the 'Kuhn-Munkres algorithm'.
The algorithm developed by Kuhn was largely based on the earlier works of two other Hungarian mathematicians: Dénes König and Jenő Egerváry. The great advantage of Kuhn’s method is that it is strongly polynomial (see Computational complexity theory for details). The main innovation of the algorithm was to combine two separate parts in Egerváry’s proof into one.

Contents

Modeling

Algorithm

Bipartite graph representation

A minimization problem

Bibliography

External links

Implementations

Modeling

The algorithm models an assignment problem as a ''n''×''m'' cost matrix, where each element represents the cost of assigning the ''i''th worker to the ''j''th job. 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 so that minimization of its elements results in maximizing the original cost values. In an infinite-cost problem, the initial cost matrix can be re-modelled by subtracting every element of each line from the maximum value of the element of that line (or column respectively). In a finite-cost problem, all the elements are subtracted from the maximum value of the whole matrix.

Algorithm

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 insufficient 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.
The procedure of obtaining the prime zeros can be implemented in a flow network, and automated by means of the Ford-Fulkerson algorithm. The ''n''×''m'' matrix is transformed in a $G=(U,V)$ bipartite graph, with I/O capacity equal to 1. Each arc joining the nodes of the flow network represents a zero in the cost matrix. After the maximum flow is obtained, the affected arcs represent the prime zeros. The minimum cut obtained by Ford-Fulkerson automates the process of marking the independent zeros. Each node that gets "cut" on the max-flow graph represents a marked column or line on the cost matrix. In the Hungarian method, assignment can be easily found on the cost matrix, yet the expansion into a max-flow sub-problem is a useful method in more complex scenarios.

Bipartite graph representation

Given $n$ worker and $n$ task vertices, and non-negative edges
$e(i,\; j)\; quad\; i,\; j\; =\; 1,...,n$
representing the cost of assigning worker $i$ to task $j$, find the cost minimizing assignment.
If using only those edges of cost 0 we can find an assignment (using, for example, the Hopcroft–Karp algorithm) then obviously that assignment is the best available.
If such a matching doesn't exist, the Hungarian algorithm adjusts the costs associated with each edge to introduce zeros without changing which edges will be used in the optimal assignment.
(1) for each worker $i$, the minimal cost associated with that worker ($m\_i\; =\; min\; \{c(i,j)\; |\; j\; =\; 1,...,n\}$) can be subtracted from the cost of each edge associated with that worker (). This replaces the minimal cost with a 0. Since in the final matching the worker must perform exactly one job, uniformly shifting the cost of all jobs associated with a worker doesn't change the optimal assignment.
(2) Likewise, for each job, the minimal associated cost can be subtracted from the cost of each edge associated with that job.
(3) We now find a maximal unweighted matching using only edges of cost 0. If this is a full matching (assignment) we are done. Otherwise, let $V$ be a minimal vertex cover of the 0 cost edges, which may be computed at the same time as the matching using König's algorithm.
(4) Partition the edges into three sets: those with no vertices in $V$ ($E\_0$), those with one vertex in V ($E\_1$), and those with both vertices in V ($E\_2$). We find the edge of smallest cost in $E\_0$, subtract this cost from all edges in $E\_0$ and add it to all edges in $E\_2$. We now return to step (3).

A minimization problem

Given $n$ workers and tasks, and an ''n''×''n'' matrix containing the cost of assigning each worker to a task, find the cost minimizing assignment.
First the problem is written in the form of a matrix as given below
:
a1 & a2 & a3 & a4\
b1 & b2 & b3 & b4\
c1 & c2 & c3 & c4\
d1 & d2 & d3 & d4end{bmatrix}
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. The matrix is square: each agent can perform only one task.
Then we perform row operations on the matrix. To do this, the lowest of all ''a''_''i'' (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.

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 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 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'

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.
Basically you find the second minimum cost among the two rows. The procedure is repeated until you are able to distinguish among the workers in terms of least cost.

Bibliography

★ Harold W. Kuhn, "The Hungarian Method for the assignment problem", ''Naval Research Logistic Quarterly'', '2':83-97, 1955. Kuhn's original publication.

★ Harold W. Kuhn, "Variants of the Hungarian method for assignment problems", ''Naval Research Logistic Quarterly'', '3': 253-258, 1956.

★ J. Munkres, "Algorithms for the Assignment and Transportation Problems", ''Journal of the Society of Industrial and Applied Mathematics'', '5'(1):32-38, 1957 March.

★ M. Fischetti, "Lezioni di Ricerca Operativa", Edizioni Libreria Progetto Padova, Italia, 1995.

★ R. Ahuja, T. Magnanti, J. Orlin, "Network Flows", Prentice Hall, 1993.

External links

★ R. A. Pilgrim, ''Munkres' Assignment Algorithm. Modified for Rectangular Matrices'', Course notes, Murray State University.

★
★ Or: Step-by-step description of algorithm

★ Mike Dawes, ''The Optimal Assignment Problem'', Course notes, University of Western Ontario.

★ On Kuhn's Hungarian Method - A tribute from Hungary, Andras Frank, Egrervary Research Group, Pazmany P. setany 1/C, H1117, Budapest, Hungary.

Implementations

★ Online interactive implementation

★ Graphical implementation with options (Java applet)

★ Serial and parallel implementations.

★ Implementation in Matlab and C

★ Perl implementation

★ Lisp implementation

★ C++ implementation