Content deleted Content added
eliminating section - restoring crucial paragraph |
|||
Line 1:
The '''Hungarian algorithm''' is a [[Optimization (mathematics)|combinatorial optimization]] [[algorithm]] which solves [[assignment problem]]s in [[polynomial time]]. 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: [[Denes König]] and [[Jenő 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 into one.
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 <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 marking the independent zeros. Each node that gets "cut" on the max-flow graph represents a marked collumn 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.▼
==Modeling==
Line 12 ⟶ 10:
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.
▲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 <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 marking the independent zeros. Each node that gets "cut" on the max-flow graph represents a marked collumn 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.
==A minimization problem==
| |||