The Hungarian algorithm: An example

We consider an example where four jobs (J1, J2, J3, and J4) need to be executed by four workers (W1, W2, W3, and W4), one job per worker. The matrix below shows the cost of assigning a certain worker to a certain job. The objective is to minimize the total cost of the assignment.

	J1	J2	J3	J4
W1	82	83	69	92
W2	77	37	49	92
W3	11	69	5	86
W4	8	9	98	23

Below we will explain the Hungarian algorithm using this example. Note that a general description of the algorithm can be found here.

Step 1: Subtract row minima

We start with subtracting the row minimum from each row. The smallest element in the first row is, for example, 69. Therefore, we substract 69 from each element in the first row. The resulting matrix is:

	J1	J2	J3	J4
W1	13	14	0	23	(-69)
W2	40	0	12	55	(-37)
W3	6	64	0	81	(-5)
W4	0	1	90	15	(-8)

Step 2: Subtract column minima

Similarly, we subtract the column minimum from each column, giving the following matrix:

	J1	J2	J3	J4
W1	13	14	0	8
W2	40	0	12	40
W3	6	64	0	66
W4	0	1	90	0
				(-15)

Step 3: Cover all zeros with a minimum number of lines

We will now determine the minimum number of lines (horizontal or vertical) that are required to cover all zeros in the matrix. All zeros can be covered using 3 lines:

	J1	J2	J3	J4
W1	13	14	0	8
W2	40	0	12	40	x
W3	6	64	0	66
W4	0	1	90	0	x
			x

Because the number of lines required (3) is lower than the size of the matrix (n=4), we continue with Step 4.

Step 4: Create additional zeros

First, we find that the smallest uncovered number is 6. We subtract this number from all uncovered elements and add it to all elements that are covered twice. This results in the following matrix:

	J1	J2	J3	J4
W1	7	8	0	2
W2	40	0	18	40
W3	0	58	0	60
W4	0	1	96	0

Now we return to Step 3.

Step 3: Cover all zeros with a minimum number of lines

Again, We determine the minimum number of lines required to cover all zeros in the matrix. Now there are 4 lines required:

	J1	J2	J3	J4
W1	7	8	0	2	x
W2	40	0	18	40	x
W3	0	58	0	60	x
W4	0	1	96	0	x

Because the number of lines required (4) equals the size of the matrix (n=4), an optimal assignment exists among the zeros in the matrix. Therefore, the algorithm stops.

The optimal assignment

The following zeros cover an optimal assignment:

	J1	J2	J3	J4
W1	7	8	0	2
W2	40	0	18	40
W3	0	58	0	60
W4	0	1	96	0

This corresponds to the following optimal assignment in the original cost matrix:

	J1	J2	J3	J4
W1	82	83	69	92
W2	77	37	49	92
W3	11	69	5	86
W4	8	9	98	23

Thus, worker 1 should perform job 3, worker 2 job 2, worker 3 job 1, and worker 4 should perform job 4. The total cost of this optimal assignment is to 69 + 37 + 11 + 23 = 140.

Solve your own problem online