|
In [[graph theory]], theThe '''Hungarian algorithm''' is ana [[algorithmOptimization|combinatorial optimization]] on [[Optimization|Combinatorial Optimizationalgorithm]], which solves instances of the [[assignment problem]]s in [[polynomial time]]. ItsThe first version, known as the '''Hungarian method''', was invented and published by [[Harold Kuhn]] in 1955. The Hungarian methodThis was in turn revised by [[James Munkres]] in 1957, and ever since it has been widelyknown knownsince as the '''Hungarian algorithm''', or the '''Munkres' assignment algorithm''', or even as the '''Kuhn-Munkres algorithm'''.
==Theory==
The algorithm developped by Kuhn was largerlylargely 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 <math>\&pi</math> ;) into one. The procedure of covering the prime zeros can be implemented in a [[flow network]], and automated by means of the [[Ford-Fulkerson algorithm]]. The nxm''n''×''m'' matrix is transformed in a <math>G=(U,V)</math> 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, will automateautomates the process of covering the independent zeros. Each node that gets "cut" on the max-flow graph, represents a covered row or line on the cost matrix. However, in the Hungarian method, the 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 scenariascenarios.
==Modelisation==
The algorithm requires to modelisemodels an assignment problem in the form ofas a NxM matrix, known as the''n''×''m'' cost matrix, in whichwhere each elemenentelement represents the cost of assigning one of the N''n''th workersworker to one ofthe M''m''th jobsjob. 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 wayso that the minimization of its elements willresults resultin to a maximization ofmaximizing the original cost values. In an infinite-cost problem, the initial cost matrix can be re-modelisedmodelled 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 the elements are subtracted from the maximum value of the whole matrix.
==Algorithm [http://www.public.iastate.edu/~ddoty/HungarianAlgorithm.html]==
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]] step 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''n''×''m'' cost matrix in which each element represents the cost of assigning one ofthe ''n''th workersworker to one ofthe ''m''th jobsjob. 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.
==A minimization problem==
Given <math>n</math> workers and tasks, and an <math>N''n''×''n'' x N</math> 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
d1 & d2 & d3 & d4\end{bmatrix}</math>
Wherewhere 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 theThe 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.
d1' 0 d3' d4' <br/>
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.
| 