Hungarian Algorithm

A Bit of History

Harold Kuhn published "The Hungarian Method for the Assignment Problem" in 1955, and deliberately chose that name to credit the two Hungarian mathematicians whose earlier theoretical work made his algorithm possible: Dénes Kőnig (whose 1931 theorem was already met in Part 16) and Jenő Egerváry, whose 1931 refinement of König's ideas supplied the key combinatorial structure Kuhn's method exploits directly. Two years later, in 1957, James Munkres revisited the method and proved it runs in strictly polynomial time — \(O(n^3)\) — which is why the algorithm is also frequently called the Kuhn-Munkres algorithm in more careful references.

Working Principle

The assignment problem: given an \(n \times n\) cost matrix \(C\) (worker \(i\) costs \(C[i][j]\) to assign to task \(j\)), find a perfect matching minimizing total cost. The Hungarian algorithm works directly on the cost matrix, in four repeated steps:

1. Row reduction: subtract each row's minimum from every entry in that row.
2. Column reduction: subtract each column's minimum from every entry in that column.
3. Cover all zeros with the minimum number of horizontal/vertical lines. If the number of lines equals \(n\), an optimal assignment exists among the zeros — stop.
4. Otherwise, adjust: find the smallest uncovered value, subtract it from every uncovered entry, and add it to every entry covered twice (where a horizontal and vertical line cross) — then return to step 3.

Worked Example

A 3×3 cost matrix (workers A, B, C; tasks 1, 2, 3):

Row reduction (subtract row minimums 9, 6, 6): rows become \([0,2,5]\), \([0,9,7]\), \([6,7,0]\). Column reduction (column minimums are now 0, 2, 0 — only column 2 needs adjustment): column 2 becomes \([0,7,5]\). Covering zeros: \((A,1)\), \((B,1)\)... but two zeros share column 1, so only 2 lines are needed to cover all zeros, not 3 — another adjustment round follows (details omitted for brevity), eventually yielding the optimal assignment \(A{\to}1, B{\to}\text{(unused zero path)}, C{\to}3\), landing on the true minimum-cost assignment \(A{\to}2, B{\to}1, C{\to}3\) with total cost \(11+6+6=23\) — matching what a brute-force check of all \(3! = 6\) possible assignments would confirm.

Why Reduction Preserves the Optimum

Formally: if you subtract a constant \(u_i\) from every entry in row \(i\) and \(v_j\) from every entry in column \(j\), any perfect matching's total cost changes by exactly \(\sum_i u_i + \sum_j v_j\) — the same amount for every possible assignment, since a perfect matching uses each row and column exactly once. So the relative ordering of assignments by cost is completely unchanged, and an assignment using only zero-cost entries in the reduced matrix must be optimal in the original matrix too — precisely the reduction-and-cover strategy the algorithm exploits, connecting back to König's theorem's matching-cover duality from Part 16 to guarantee that "enough zeros for a full assignment" is always eventually reachable.

Complexity Analysis

Munkres' 1957 analysis established:

$$\text{Time: } O(n^3) \qquad \text{Space: } O(n^2)$$

where \(n\) is the number of workers/tasks — polynomial, and (unlike Ford-Fulkerson) independent of the actual cost values involved.

Implementation

def hungarian_algorithm(cost):
    """
    cost: n x n matrix (list of lists). Minimizes total assignment cost.
    Returns (row_to_col_assignment, total_cost) using the Jonker-Volgenant-style
    potential/augmenting formulation (equivalent result to the classical method).
    """
    n = len(cost)
    INF = float('inf')
    u = [0] * (n + 1)
    v = [0] * (n + 1)
    p = [0] * (n + 1)   # p[j] = row assigned to column j (1-indexed, 0 = unassigned)
    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, j1 = minv[j], 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:
            j1 = way[j0]
            p[j0] = p[j1]
            j0 = j1

    assignment = [0] * n
    total_cost = 0
    for j in range(1, n + 1):
        if p[j] != 0:
            assignment[p[j] - 1] = j - 1
            total_cost += cost[p[j] - 1][j - 1]

    return assignment, total_cost

cost = [[9, 11, 14], [6, 15, 13], [12, 13, 6]]
assignment, total = hungarian_algorithm(cost)
print(assignment, total)   # [1, 0, 2]  23  -- worker0->task1, worker1->task0, worker2->task2

#include <vector>
#include <limits>
#include <iostream>
using namespace std;

pair<vector<int>, int> hungarianAlgorithm(vector<vector<int>>& cost) {
    int n = cost.size();
    const int INF = numeric_limits<int>::max();
    vector<int> u(n + 1, 0), v(n + 1, 0), p(n + 1, 0), way(n + 1, 0);

    for (int i = 1; i <= n; i++) {
        p[0] = i;
        int j0 = 0;
        vector<int> minv(n + 1, INF);
        vector<bool> used(n + 1, false);
        do {
            used[j0] = true;
            int i0 = p[j0], delta = INF, j1 = -1;
            for (int j = 1; j <= n; j++) {
                if (!used[j]) {
                    int 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 (int j = 0; j <= n; j++) {
                if (used[j]) { u[p[j]] += delta; v[j] -= delta; }
                else minv[j] -= delta;
            }
            j0 = j1;
        } while (p[j0] != 0);

        while (j0) {
            int j1 = way[j0];
            p[j0] = p[j1];
            j0 = j1;
        }
    }

    vector<int> assignment(n);
    int totalCost = 0;
    for (int j = 1; j <= n; j++) {
        assignment[p[j] - 1] = j - 1;
        totalCost += cost[p[j] - 1][j - 1];
    }
    return {assignment, totalCost};
}

int main() {
    vector<vector<int>> cost = {{9, 11, 14}, {6, 15, 13}, {12, 13, 6}};
    auto [assignment, total] = hungarianAlgorithm(cost);
    cout << "Total cost: " << total << endl;  // 23
    return 0;
}

import java.util.*;

class HungarianAlgorithm {
    static int[] solve(int[][] cost, int[] totalCostOut) {
        int n = cost.length;
        int[] u = new int[n + 1], v = new int[n + 1], p = new int[n + 1], way = new int[n + 1];
        int INF = Integer.MAX_VALUE;

        for (int i = 1; i <= n; i++) {
            p[0] = i;
            int j0 = 0;
            int[] minv = new int[n + 1];
            boolean[] used = new boolean[n + 1];
            Arrays.fill(minv, INF);

            do {
                used[j0] = true;
                int i0 = p[j0], delta = INF, j1 = -1;
                for (int j = 1; j <= n; j++) {
                    if (!used[j]) {
                        int 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 (int j = 0; j <= n; j++) {
                    if (used[j]) { u[p[j]] += delta; v[j] -= delta; }
                    else minv[j] -= delta;
                }
                j0 = j1;
            } while (p[j0] != 0);

            while (j0 != 0) {
                int j1 = way[j0];
                p[j0] = p[j1];
                j0 = j1;
            }
        }

        int[] assignment = new int[n];
        int totalCost = 0;
        for (int j = 1; j <= n; j++) {
            assignment[p[j] - 1] = j - 1;
            totalCost += cost[p[j] - 1][j - 1];
        }
        totalCostOut[0] = totalCost;
        return assignment;
    }

    public static void main(String[] args) {
        int[][] cost = {{9, 11, 14}, {6, 15, 13}, {12, 13, 6}};
        int[] totalCost = new int[1];
        int[] assignment = solve(cost, totalCost);
        System.out.println("Total cost: " + totalCost[0]);  // 23
    }
}

Real-World Applications

Exercises

1. Complete the worked example by hand through all reduction rounds, confirming the final assignment and its total cost of 23.
2. Explain why subtracting a row's minimum from every entry in that row never changes which assignment is optimal, using the "shared constant shift" argument from the correctness section.
3. Modify a cost matrix to maximize total value instead of minimizing cost (hint: negate every entry, or subtract every entry from a large constant), and verify the Hungarian algorithm still produces the correct optimal assignment.
4. Challenge: Handle an unbalanced assignment problem (more workers than tasks, or vice versa) by padding the cost matrix with dummy rows/columns of cost 0, and verify the algorithm still produces a sensible partial assignment.

Limitations