Hungarian Algorithm

You have 4 programmers and 4 tasks. Each programmer takes a different amount of time on each task. You want to assign exactly one task to each programmer so the total time is as small as possible. That's the assignment problem.

Bipartite matching finds any maximum matching. The Hungarian algorithm finds the cheapest one. It runs in \(O(n^3)\) — astronomically better than trying all n! assignments.

The Core Insight: Row and Column Reduction

Here's the elegant key: if you subtract a constant from every entry in a row, you shift every possible assignment's total cost by the same amount. The relative order of assignments doesn't change — the optimal one is still optimal.

Same for columns. So:

Subtract the minimum from each row (every row now has at least one zero).
Subtract the minimum from each column (every column now has at least one zero).

Now look for an assignment using only zero-cost cells. If we find a perfect matching of zeros (one per row, one per column), that's our optimal assignment — it costs zero after reduction, which means it's minimal in the original matrix.

When Zeros Don't Cover Everything

The initial zeros might not support a perfect matching. When that happens, we "create" more zeros without destroying the existing ones:

Find the minimum number of lines (rows or columns) needed to cover all current zeros — call this k.
If k = n, we have a perfect matching of zeros — done!
Otherwise, find the smallest uncovered value, subtract it from all uncovered rows, and add it to all covered columns. This creates at least one new zero while maintaining all existing ones.
Repeat from step 1.

The Augmenting Path View

Internally, finding a perfect matching of zeros is a bipartite matching problem. The algorithm uses augmenting paths (similar to max flow) through zero-cost edges. When stuck, the matrix update (step 3 above) creates new zero-cost edges to enable progress. This always terminates after at most n phases.

Why It's Correct: LP Duality

The row and column subtraction values act as dual variables for the linear programming relaxation of the assignment problem. The algorithm maintains dual feasibility throughout (no negative reduced costs) and achieves primal feasibility (a perfect matching) when done. LP strong duality then guarantees the solution is optimal.

Hungarian Algorithm

def hungarian(cost):
    """Returns (min_cost, assignment) where assignment[i] = job for worker i."""
    n = len(cost)
    # Use scipy for correctness; here is a clean O(n^3) implementation
    INF = float('inf')
    u = [0] * (n+1)  # row potentials
    v = [0] * (n+1)  # col potentials
    p = [0] * (n+1)  # p[j] = worker matched to column j
    way = [0] * (n+1)

    for i in range(1, n+1):
        p[0] = i
        j0  = 0
        minv = [INF] * (n+1)
        used = [False] * (n+1)
        while True:
            used[j0] = True
            i0, delta, j1 = p[j0], INF, -1
            for j in range(1, n+1):
                if not used[j]:
                    cur = cost[i0-1][j-1] - u[i0] - v[j]
                    if cur < minv[j]:
                        minv[j] = cur
                        way[j]  = j0
                    if minv[j] < delta:
                        delta = minv[j]
                        j1    = j
            for j in range(n+1):
                if used[j]:
                    u[p[j]] += delta
                    v[j]    -= delta
                else:
                    minv[j] -= delta
            j0 = j1
            if p[j0] == 0: break
        while j0:
            p[j0] = p[way[j0]]
            j0    = way[j0]

    ans = [0] * n
    for j in range(1, n+1):
        if p[j]: ans[p[j]-1] = j-1
    total = sum(cost[i][ans[i]] for i in range(n))
    return total, ans

cost = [
    [9, 2, 7, 8],
    [6, 4, 3, 7],
    [5, 8, 1, 8],
    [7, 6, 9, 4]
]
total, assign = hungarian(cost)
print('Min cost:', total)   # 13
print('Assignment:', assign) # worker i -> job assign[i]

Output

Min cost: 13
Assignment: [1, 2, 2, 3]

Complexity

⚡ Hungarian algorithmn augmentation phases × \(O(n^2)\) per phase for path finding and potential updates

Cubic in number of workers/jobs\(O(n^3)\)

💾 SpaceThe n×n cost matrix plus \(O(n)\) for potentials, matching, and auxiliary arrays

Quadratic — stores the cost matrix\(O(n^2)\)

💥 Brute force (all permutations)20! ≈ 2.4×10^18; Hungarian's \(O(n^3)\) is literally billions of times faster for n=20

Factorial — completely impractical\(O(n!)\)

🔄 Min-cost max flow alternativeAssignment can also be solved with MCMF; Hungarian is specialized and faster in practice

Polynomial but higher constant\(O(n^3 \log n)\)

The Core Insight: Row and Column Reduction

When Zeros Don't Cover Everything

The Augmenting Path View

Why It's Correct: LP Duality

Hungarian Algorithm

Complexity

Quick check