Hungarian Algorithm¶

Definition¶

The Hungarian algorithm solves the square minimum-cost assignment problem. Subtract each row minimum, then each column minimum. Cover all zeros of the resulting matrix with a minimum number of rows and columns. If $n$ lines are needed, select $n$ independent zeros, one per row and column. Otherwise let $k$ be the smallest uncovered entry, subtract $k$ from uncovered entries, add $k$ to doubly covered entries, leave singly covered entries unchanged, and repeat the covering step.

Interpretation¶

The Hungarian algorithm changes the cost table, without changing which assignment is best, until it contains a complete assignment made of zeros. Since all entries stay nonnegative, such a zero assignment is optimal.

Four 3 by 3 matrices in a row: the costs, after subtracting row minima, after subtracting column minima with two covering lines, and after an adjustment with three independent zeros marking the optimal assignment.

Subtracting the row minima $2,3,1$ and then the column minima $1,0,4$ gives the third table, whose zeros can be covered by two lines. Two lines are fewer than three, so no complete zero assignment exists yet. The adjustment by the smallest uncovered entry $1$ creates the fourth table, where the three green zeros form the optimal assignment with original cost $4+7+1=12$ $12$ .

Each step is an assignment cost transformation. The adjustment equals subtracting $k$ from every uncovered row and adding $k$ to every covered column: uncovered entries lose $k$ , doubly covered entries gain $k$ , and singly covered entries are unchanged. The constants subtracted in the figure add up to $6+5+1=12$ $12$ , exactly the optimal cost: every complete assignment costs at least that total, and the zero assignment attains it.

The number of lines must be the minimum, found by a minimum zero cover: it equals the largest number of zeros with no two in the same row or column, so $n$ lines mean that a complete zero assignment exists. That largest set of zeros is a largest matching on the zero entries, which can be found as a maximum flow.

Key Results¶

The zero cover must use the minimum number of lines.
A set of independent zeros has no two in the same row or column.
The minimum line-cover size equals the maximum number of independent zero assignments in this construction.
Do not add together transformed zero costs to report the original objective value.

Examples¶

In the figure, the smallest uncovered entry is 1: subtract 1 from uncovered entries, add 1 at double intersections, and leave singly covered entries unchanged. The final zero assignment $(1,1),(2,3),(3,2)$ has original cost $4+7+1=12$ $12$ .

The worked four-machine matrix initially needs three covering lines; an adjustment with $k=2$ enables a complete assignment.
The final original cost is $2+5+6+7=20$ $20$ .

Prerequisites¶

Sources¶

OR Modelling · Week 5

Aliases: Hungarian method, Kuhn-Munkres algorithm, Munkres algorithm, Kuhn-Munkres method

Last updated: 20 October 2026 03:02