The algorithm developped by Kuhn was largely based on the earlier works of two other [[Hungarian]] mathematicians: [[KonigDenes Kőnig]] and [[EgervaryJenő Egerváry]]. 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. The procedure of covering 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 <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 automates 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 scenarios.
==Modelisation==
Line 92:
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.
==Bibliography==
* Harold W. Kuhn, "The Hungarian Method for the assignment problem", ''Naval Research Logistic Quarterly'' '''2''' (1955), pp. 83-97. Kuhn's original publication.
