You have n workers and n tasks, and a matrix giving the cost of each worker doing each task. Assign exactly one worker per task to minimize the total cost. Trying all matchings is n! — hopeless. The Hungarian algorithm solves it in polynomial time with a lovely idea: subtracting a constant from an entire row (or column) doesn’t change which assignment is best, only its total. So reduce each row by its minimum, then each column by its minimum, until enough zeros appear that you can pick n of them with no two in the same row or column — that set of zeros is the optimal assignment. Reduce the matrix and watch the answer surface.
O(n³) · subtracting a whole row/column preserves the best assignment · zeros mark the choices
cost matrix
Entry [i][j] = cost of assigning worker i to task j.
the invariant
Subtracting a constant from a whole row or column keeps the optimal assignment the same.
row / column reduce
Subtract each row’s minimum, then each column’s minimum, creating zeros.
independent zeros
n zeros with no two sharing a row or column — the optimal assignment.
hungarian.js — reduce, then match the zeros
Ready
A 4×4 cost matrix (workers × tasks). We’ll subtract each row’s minimum, then each column’s, to create zeros marking cheap options — then pick 4 independent zeros. Step through the reduction.
start
phase
0
zeros
–
optimal cost
How it works
The whole method rides on one fact: if you subtract a constant c from every entry in a single row, then every complete assignment (which uses exactly one entry from that row) drops by exactly c — so the ranking of assignments is unchanged, and the cheapest stays cheapest. The same holds for columns. So you can freely reduce rows and columns to manufacture zeros without disturbing the optimum. Reduce each row by its minimum, then each column by its minimum; the zeros now mark, for each worker and each task, its locally-cheapest options. If you can select n zeros with no two in the same row or column, that selection is a zero-cost assignment in the reduced matrix — and therefore the minimum-cost assignment in the original. When zeros can’t yet be matched fully (they bunch up), the algorithm covers all zeros with the fewest lines and adjusts uncovered entries to create new zeros, repeating until a full matching exists.
1
Reduce each row
Subtract the smallest entry of each row from that whole row. Every row now has at least one zero, and the best assignment is unchanged.
2
Reduce each column
Subtract the smallest entry of each column from that whole column. More zeros appear, still without changing which assignment is optimal.
3
Match independent zeros
Try to select n zeros with no two in the same row or column. If you can, those positions are the optimal assignment — read off the original costs and sum them.
✓
Cover-and-adjust if stuck
If the zeros can’t all be matched, cover every zero with the minimum number of lines, subtract the smallest uncovered value from uncovered entries (and add it at line crossings), creating new zeros. Repeat until a full matching exists — all in O(n³).
Time
O(n³)
vs brute force
O(n!)
Finds
optimal assignment
Key move
row/col reduce
The code
# Hungarian algorithm, core reduction (O(n^3) full version adds covering)for i in range(n): # row reduction
m = min(cost[i])
for j in range(n): cost[i][j] -= m
for j in range(n): # column reduction
m = min(cost[i][j] for i in range(n))
for i in range(n): cost[i][j] -= m
# now select n independent zeros (an assignment of zero reduced-cost).# if impossible: cover all zeros with fewest lines, subtract the min# uncovered value from uncovered cells (add at crossings), repeat.
Quick check
1. What operation does the Hungarian algorithm rely on to create zeros without changing the answer?
Subtracting c from a whole row lowers every complete assignment by exactly c (each uses one entry of that row), so the optimal assignment is unchanged. This lets you manufacture zeros freely.
2. What do you look for after reducing rows and columns?
A set of n zeros with no two sharing a row or column is a zero-cost assignment in the reduced matrix, and therefore the minimum-cost assignment in the original.
3. How does the Hungarian algorithm beat the brute-force O(n!) approach?
Rather than trying all n! assignments, it reduces the matrix and finds a matching among zeros (with cover-and-adjust when needed) in O(n³) — polynomial time for a problem that is factorial by brute force.
FAQ
What is the Hungarian algorithm?
The Hungarian (Kuhn–Munkres) algorithm solves the assignment problem: given an n×n cost matrix, assign one worker per task to minimize total cost, in O(n³). It reduces rows and columns to create zeros and finds a matching among them, adjusting the matrix when a full matching isn’t yet possible.
Why does subtracting a row or column constant not change the optimal assignment?
A complete assignment uses one entry per row and column. Subtracting c from a whole row lowers every assignment’s total by exactly c, so all shift equally and the cheapest stays cheapest (same for columns). Hence you can reduce to create zeros without changing the optimal assignment.
What is the assignment problem used for?
Assigning workers to jobs, machines to tasks, or agents to targets at minimum cost; data association in tracking and vision; scheduling; and as a subroutine in larger optimizations — any one-to-one matching with per-pair costs where you want the cheapest overall matching.
How does the Hungarian algorithm relate to min-cost max-flow?
The assignment problem is a special case of min-cost max-flow: a bipartite source→workers→tasks→sink graph with unit capacities and assignment costs, solved by a min-cost flow of value n. The Hungarian algorithm is a specialized, often faster O(n³) method for that structure.