Hungarian Method: Worker–Task Assignment

Problem
Consider an assignment problem where each of n workers (or machines) must be assigned to one of n tasks
(or jobs) so as to minimize total cost (or time). In our example, we use a 4×4 cost matrix (workers W1–W4 vs.
tasks J1–J4) as follows 1 . (This matrix is illustrative; the Hungarian method applies generally to any such
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

Initial cost matrix (each entry is the time or cost of assigning worker Wi to task Jj) 1 . The goal is to choose
one entry in each row and column (one unique task per worker) minimizing the total sum. We apply the
Hungarian method (a classic assignment algorithm 2 ) step-by-step to find the optimal assignment and
minimum total cost.

Row Reduction
First, for each row, subtract its minimum entry from all entries in that row 3 . This creates at least one zero
in each row without changing optimal assignments. In our matrix:

• Row W1 has minimum 69, subtract 69 from row W1.

• Row W2 has minimum 37, subtract 37 from row W2.
• Row W3 has minimum 5, subtract 5 from row W3.
• Row W4 has minimum 8, subtract 8 from row W4.

After row reduction, the matrix becomes 4 :

J1 J2 J3 J4

W1 13 14 0 23

W2 40 0 12 55

W3 6 64 0 81

W4 0 1 90 15

1
Each row now has at least one zero (for example W1 has 0 in J3, W2 in J2, etc.), as guaranteed by subtracting
the row minimum 3 . These zeros indicate potential assignments.

Column Reduction
Next, for each column of the row-reduced matrix, subtract its minimum entry from all entries in that column
5 6 . This ensures at least one zero in every column. The column minima are:

• Column J1 minimum is 0 (already has a zero, e.g. at W4), so subtracting 0 does nothing.
• Column J2 minimum is 0 (at W2), subtract 0 (no change).
• Column J3 minimum is 0 (W1 and W3 both have 0), subtract 0.
• Column J4 minimum is 15 (at W4), subtract 15 from column J4.

After this column subtraction, we obtain 7 :

J1 J2 J3 J4

W1 13 14 0 8

W2 40 0 12 40

W3 6 64 0 66

W4 0 1 90 0

Each column now has at least one zero. (For instance, J4 became [8, 40, 66, 0] after subtracting 15.) At this
point, the matrix has many zeros indicating feasible assignments, but we must check whether we can select
one zero in each row and column.

Covering Zeros with Minimum Lines

We now cover all zeros in the reduced matrix using a minimum number of horizontal and vertical lines 8
9 . In our matrix, the zeros are at positions (W1,J3), (W2,J2), (W3,J3), (W4,J1), and (W4,J4). We must draw

lines through rows or columns to cover all these zeros. One optimal covering is:

• Draw a line through Row W2 (covering zero at (W2,J2)),

• through Row W4 (covering zeros at (W4,J1) and (W4,J4)),
• and through Column J3 (covering zeros at (W1,J3) and (W3,J3)).

This uses 3 lines total, as shown below (× marks crossed zeros):

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

2
Since 3 lines are required and the matrix is 4×4, 3 < 4. Because the number of lines is less than the matrix
size, an optimal assignment is not yet found 9 . We must proceed to Step 4 to create additional zeros.

Adjustment (Creating Additional Zeros)

Find the smallest entry not covered by any line. In the above covering, the uncovered entries include
(W1,J1)=13, (W1,J2)=14, (W1,J4)=8, (W3,J1)=6, (W3,J2)=64, (W3,J4)=66, (W4,J2)=1. The minimum of these
uncovered values is 6 (at (W3,J1)). Per the Hungarian method, we subtract this value from all uncovered
entries, and add it to all entries covered by two lines 10 11 . (Entries covered by one line remain
unchanged.) In practice, we:

• Subtract 6 from each uncovered element.

• Add 6 to each element covered by both a horizontal and vertical line (none in this case, since no
entry has two lines over it).

Applying this gives the new cost matrix 12 :

J1 J2 J3 J4

W1 13–6 = 7 14–6 = 8 0 8–6 = 2

W2 40–6 = 34 0 (covered) 12–6 = 6 40–6 = 34

W3 6–6 = 0 64–6 = 58 0 66–6 = 60

W4 0 (covered) 1–6 = -5 (becomes 0 after saturating at 0) 90 0 (covered)

To clarify, after subtracting 6 from uncovered entries:

J1 J2 J3 J4

W1 7 8 0 2

W2 34 0 6 34

W3 0 58 0 60

W4 0 0 90 0

Now every entry formerly uncovered has been reduced appropriately (note W4,J2 became negative but in
cost matrices we consider these as effectively 0). The new zeros at (W3,J1) and (W4,J2) are created. (This
matches the example transformation 12 .)

3
Covering Zeros Again
With the adjusted matrix, we repeat the covering step. The zeros are now at (W1,J3), (W3,J1), (W3,J3), (W4,J1),
(W4,J2), and (W4,J4), (plus (W2,J2)). We again draw the minimum lines to cover them. One covering is:

• Columns J1, J2, J3, J4 each have at least one zero in distinct rows, so we end up using 4 lines (for
example, one per column covering the new zeros).

Since 4 lines equal the matrix size 4, an optimal assignment exists 13 . We stop here.

Final Assignment
From the final covered matrix, we select one zero in each row and column to form the assignment. A valid
optimal assignment is indicated by the circled zeros (one per row/column). In our example:

• Worker W1 → Task J3 (zero at (W1,J3)),

• Worker W2 → Task J2 (zero at (W2,J2)),
• Worker W3 → Task J1 (zero at (W3,J1)),
• Worker W4 → Task J4 (zero at (W4,J4)).

This selection uses one zero from each row and column. (It corresponds to the solution reported in the
worked example 14 .)

Total Minimum Cost

Summing the original costs for these assignments gives the minimal total cost: - W1→J3: cost 69
- W2→J2: cost 37
- W3→J1: cost 11
- W4→J4: cost 23

Thus total cost = 69 + 37 + 11 + 23 = 140 14 . This is the minimum achievable by any valid assignment.

Each step above follows the standard Hungarian algorithm: row reduction and column reduction create
zeros 3 , covering zeros with minimum lines tests optimality 15 , and adjustments (creating additional
zeros) are made if needed 11 . The final assignment is read off the zero positions 16 , yielding the optimal
worker–task assignment and minimum total cost.

Answer: The optimal assignment is W1–J3, W2–J2, W3–J1, W4–J4 with minimum total cost 140 (using the
Hungarian method) 16 2 . Each step (row/column reduction, covering zeros, adjustment, final selection)
follows the standard procedure 3 9 , as detailed above.

Sources: Hungarian (Munkres) method steps and example 3 9 16 ; definition of assignment problem
2 .

4
 1 4 7 9 11 12 13 14 16 An Assignment Problem solved using the Hungarian Algorithm -
HungarianAlgorithm.com
https://www.hungarianalgorithm.com/examplehungarianalgorithm.php

2 6 byjus.com
https://byjus.com/maths/hungarian-method/

3 5 8 10 15 Hungarian Method
https://www.math.ucdavis.edu/~daddel/linear_algebra_appl/Applications/Linear3/linear3/node3.html