Hungarian algorithm: Difference between revisions

Revision as of 15:26, 11 May 2006

Revision as of 09:32, 9 June 2006

Line 11:

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 collumncolumn 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==