Hungarian Algorithm to solve Assignment Problem

## Hungarian Algorithm to solve Assignment Problem

The **Hungarian algorithm of assignment** is an efficient algorithm of finding an optimal solution to the assignment problem. Hungarian method is applicable to a Balanced Assignment problem, i.e., number of rows equals to the number of columns of an assignment problem.

## Step by Step procedure

*Hungarian algorithm of assignment* involves following steps :

#### Step 1

Subtract the minimum of each row of the cost matrix,from all the elements of respective rows.

#### Step 2

Subtract the minimum of each column of the modified cost matrix, from all the elements of respective columns.

#### Step 3

Then draw the minimum number of horizontal and vertical line to cover all the zeros in the modified cost matrix.

Let the number of lines be $N$.

- If $N = n$, the number of rows (columns) of given cost matrix, then an optimal assignment can be made. Go to Step 6.
- If $N < n$, then go to next step.

#### Step 4

Determine the smallest element in the matrix, not covered by the $N$ lines. Subtract this smallest element from all the uncovered elements and add the same element at the intersection of horizontal and vertical lines. And obtain the second modified matrix.

#### Step 5

Repeat Steps 3 and 4 until minimum number of lines become equal to the number of rows (columns) of the given matrix i.e. $N =n$.

#### Step 6

Examine the row successively until a row-wise exactly single zero is found, mark this zero by $\square$ to make the assignment and mark cross $(\times)$ over all zeros in that column. Continue in this manner until all the rows have been examined. Repeat the same procedure for columns also.

#### Step 7

Repeat the Step 6 successively until one of the following situations arise :

- if no unmarked zero is left, the process ends; or
- if there lie more than one of the unmarked zeros in any column or row, then mark $\square$ one of the unmarked zeros arbitrarily and cross over all zeros lying in that row or column. Repeat the process until no unmarked zero is left in the matrix.

#### Step 8

Thus, in each row and in each column exactly one marked $\square$ zero is obtained. The assignment corresponding to these marked zeros will give an optimal assignment.

## Endnote

In this tutorial, you learned about step by step procedure of Hungarian Algorithm to solve assignment problem.

To learn more about Assignment problems please refer to the following tutorials:

Read step by step solution

Let me know in the comments if you have any questions on **Hungarian Algorithm to solve Assignment problems** and your thought on this article.