Hungarian algorithm: Difference between revisions

Revision as of 15:35, 1 February 2006

Revision as of 15:38, 1 February 2006

Line 1:

In [[graph theory]], the '''Hungarian algorithm''' is an [[algorithm]] on [[Combinatorial Optimization]], which solves instances of the [[assignment problem]] in [[polynomial time]]. Its first version, known as the '''Hungarian method''', was invented and published by [[Harold Kuhn]] in 1955. The Hungarian method was in turn revised by [[James Munkres]] in 1957, and ever since it has been widely known as the '''Hungarian algorithm''', or the '''Munkres' assignment algorithm''', or even as the '''Kuhn-Munkres algorithm'''.

The '''Hungarian''' or '''Munkres''' algorithm is a method for solving the linear [[Assignment_problem]]: Given <math>n</math> workers and tasks, and an <math>N x N</math> matrix containing the cost of assigning each worker to a task, find the cost minimizing assigment. The algorithm works in polynomial time.

==Theory==

Line 29:

:'''DONE''': Assignment pairs are indicated by the positions of the starred zeros in the cost matrix. If C(i,j) is a starred zero, then the element associated with row i is assigned to the element associated with column j.

==Example of aA minimization problem==

The '''Hungarian''' or '''Munkres''' algorithm is a method for solving the linear [[Assignment_problem]]: Given <math>n</math> workers and tasks, and an <math>N x N</math> matrix containing the cost of assigning each worker to a task, find the cost minimizing assigment. The algorithm works in polynomial time.

First the problem is written in the form of a matrix as given below

Line 39 ⟶ 41:

d1 & d2 & d3 & d4\end{bmatrix}</math>

Where a,b,c and d are the agentsworkers 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 the 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.