12.12 Hungarian Algorithm

Problem

You need to solve an assignment problem exactly.

There are n workers and n tasks. Each worker can be assigned to exactly one task, and each task can be assigned to exactly one worker. Every worker-task pair has a cost.

The goal is to minimize total cost.

Example:

Worker	Job A	Job B	Job C
Alice	8	2	7
Bob	6	4	3
Carol	5	8	1

A brute-force solution tries all permutations of jobs. That works for three workers, but it fails quickly because the number of assignments is n!.

The Hungarian algorithm solves the same problem in polynomial time.

Solution

Use the Hungarian algorithm to transform the cost matrix while preserving the identity of the optimal assignment.

The method depends on one key invariant:

Adding or subtracting the same value from every entry in a row or column changes every complete assignment by the same amount.

Therefore, the optimal assignment does not change.

The algorithm uses this invariant to create zeros in the cost matrix. Then it finds a perfect matching among zero entries. If a perfect zero matching exists, that matching is optimal.

Matrix Model

Represent the instance as an n × n matrix:

cost[i][j]

where:

i = worker
j = task

For the example:

	A	B	C
Alice	8	2	7
Bob	6	4	3
Carol	5	8	1

An assignment chooses one value from each row and each column.

For example:

Worker	Task	Cost
Alice	B	2
Bob	C	3
Carol	A	5

Total cost:

2 + 3 + 5 = 10

Why Row and Column Reductions Are Safe

Suppose you subtract x from every entry in row i.

Every complete assignment must choose exactly one entry from row i.

So every complete assignment decreases by exactly x.

The relative ordering of assignments does not change.

The same argument applies to columns.

This is the central reason the algorithm can alter the matrix without altering the answer.

Step 1: Row Reduction

For each row:

1. Find the smallest value.
2. Subtract it from every entry in that row.

Original matrix:

	A	B	C
Alice	8	2	7
Bob	6	4	3
Carol	5	8	1

Row minima:

Row	Minimum
Alice	2
Bob	3
Carol	1

After row reduction:

	A	B	C
Alice	6	0	5
Bob	3	1	0
Carol	4	7	0

Each row now contains at least one zero.

Step 2: Column Reduction

For each column:

1. Find the smallest value.
2. Subtract it from every entry in that column.

Column minima after row reduction:

Column	Minimum
A	3
B	0
C	0

After column reduction:

	A	B	C
Alice	3	0	5
Bob	0	1	0
Carol	1	7	0

Now every row and every column has at least one zero.

Step 3: Find a Zero Matching

Build a bipartite graph from the zero entries.

Create an edge:

worker -> task

when:

reducedCost[worker][task] = 0

For the reduced matrix:

Worker	Zero columns
Alice	B
Bob	A, C
Carol	C

A perfect zero matching exists:

Worker	Task
Alice	B
Bob	A
Carol	C

This corresponds to original cost:

2 + 6 + 1 = 9

So the optimal assignment has cost 9.

Step 4: If No Perfect Zero Matching Exists

Sometimes the zeros do not contain a complete assignment.

Example:

	A	B	C
Alice	0	2	3
Bob	0	4	5
Carol	0	1	2

All zeros are in column A.

Only one worker can be assigned to A, so no perfect zero matching exists.

The algorithm must create more zeros without changing the optimal assignment.

Step 5: Cover Zeros with Minimum Lines

Cover all zero entries using the minimum number of horizontal and vertical lines.

If the number of lines is n, a perfect assignment among zeros exists.

If the number of lines is less than n, continue adjusting the matrix.

For the previous example, one vertical line over column A covers all zeros.

Number of lines:

1 < 3

So more work is needed.

Step 6: Adjust the Matrix

Find the smallest uncovered value.

Call it:

δ

Then:

1. Subtract δ from every uncovered entry.
2. Add δ to every entry covered twice.
3. Leave entries covered once unchanged.

This preserves the assignment structure while creating at least one new zero.

Example:

	A	B	C
Alice	0	2	3
Bob	0	4	5
Carol	0	1	2

Cover column A.

Uncovered entries are in columns B and C.

Smallest uncovered value:

δ = 1

Subtract 1 from uncovered entries:

	A	B	C
Alice	0	1	2
Bob	0	3	4
Carol	0	0	1

A new zero appears at:

Carol -> B

Repeat matching and adjustment until a perfect zero matching exists.

Operational Algorithm

The common high-level version is:

Hungarian(cost):

    reduce all rows

    reduce all columns

    while no perfect matching among zeros:

        cover zeros with minimum number of lines

        δ = smallest uncovered value

        subtract δ from uncovered entries

        add δ to entries covered twice

    return perfect matching among zeros

This formulation is easy to teach and reason about.

Many production implementations use a potential-based form that avoids explicitly drawing cover lines, but the invariant is the same.

Pseudocode Version

Hungarian(cost):

    n = number of rows

    for each row i:
        m = min(cost[i][j])
        for each column j:
            cost[i][j] -= m

    for each column j:
        m = min(cost[i][j])
        for each row i:
            cost[i][j] -= m

    repeat:

        matching = maximum matching using zero entries

        if size(matching) == n:
            return matching

        cover = minimum line cover of zero entries

        delta = minimum uncovered entry

        for each cell (i, j):

            if cell is uncovered:
                cost[i][j] -= delta

            else if cell is covered twice:
                cost[i][j] += delta

The line cover can be derived from the failed zero matching using alternating paths, closely related to Konig's theorem for bipartite graphs.

Rectangular Matrices

If the number of workers and tasks differs, pad the smaller side with dummy rows or columns.

Example:

workers = 3
tasks = 5

Add two dummy workers.

Assign zero cost to dummy assignments if unassigned tasks are allowed.

If leaving a task unfilled has a penalty, use that penalty instead.

The result becomes a square matrix.

Maximization Problems

The Hungarian algorithm is usually stated for minimization.

For maximum-profit assignment, convert profit to cost.

Given:

profit[i][j]

define:

cost[i][j] = maxProfit - profit[i][j]

where maxProfit is the largest value in the matrix.

The assignment with minimum converted cost has maximum original profit.

Implementation Notes

Use integer costs when possible. The algorithm is exact and stable with integers.

For floating-point costs, comparisons against zero require care. In practice, use a tolerance:

abs(x) < eps

but be aware that this can create ambiguous matchings.

For large matrices, the potential-based O(n^3) implementation is preferable to the educational line-cover version because it is simpler to make efficient.

Complexity

The classical efficient implementation runs in:

O(n³)

Memory use is:

O(n²)

for the cost matrix, plus linear auxiliary arrays.

The line-cover presentation is useful conceptually, but naive implementations can exceed the intended complexity. For production code, use a standard potential-array implementation.

Common Mistakes

Returning Any Zero Matching Too Early

A zero matching must have size n.

A partial zero matching is not a complete assignment.

Modifying Covered-Once Cells

During matrix adjustment, cells covered by exactly one line remain unchanged.

Using the Reduced Cost as the Final Cost

The final assignment is selected from the reduced matrix, but its cost must be computed from the original matrix.

Forgetting Dummy Rows or Columns

Rectangular assignment problems must be converted carefully. Dummy costs should represent the real meaning of leaving something unmatched.

Confusing Minimum Cover with Arbitrary Cover

The adjustment step requires a minimum line cover. An arbitrary cover may break the algorithm.

Discussion

The Hungarian algorithm is a good example of an algorithm that works by changing the representation of a problem rather than directly searching the answer space. It preserves the optimal assignment while reshaping the matrix until the optimum is visible as a perfect matching among zeros.

This connects assignment, matching, duality, and linear programming. Row and column reductions correspond to dual variables. Zero entries correspond to tight constraints. The final perfect zero matching satisfies complementary slackness, although you do not need linear programming language to implement the algorithm.

Takeaway

The Hungarian algorithm solves the square assignment problem in O(n³) time. It repeatedly transforms the cost matrix without changing the optimal assignment, creates zero-cost candidate edges, and finds a perfect matching among those zeros.

For pure one-to-one assignment, it is usually the standard exact algorithm. For assignments with capacities, quotas, supplies, demands, or path constraints, use minimum-cost flow instead.