Hungarian Algorithm

The Assignment Problem

Suppose worker $i$ can perform task $j$ at cost $c_{ij}$. We must choose exactly one task for every worker and exactly one worker for every task. If permutation $\pi$ records the chosen task for each worker, the optimization problem is

Graphically, workers and tasks form the two sides of a weighted bipartite graph. A feasible assignment is a perfect matching; the goal is the perfect matching with minimum total edge weight. Brute force checks $n!$ permutations. The Hungarian algorithm reaches an optimum in $O(n^3)$ time.

Intuition: Prices and Tight Edges

Think of each row and column as carrying a price. After subtracting those prices, the remaining entry is a reduced cost: how much more expensive that pairing is than the current lower-bound explanation. A zero is a tight edge—a pairing whose original cost is fully explained by the current prices.

Two Views of the Same Algorithm

The familiar matrix presentation is excellent for hand calculation:

1. Row reduction: subtract the minimum of each row.
2. Column reduction: subtract the minimum of each column.
3. Zero graph: connect a row to a column wherever the reduced entry is zero, then find a maximum matching.
4. Stop or expose: a matching of size $n$ is optimal. Otherwise, use a minimum vertex cover of the zero graph to mark rows and columns.
5. Adjust: subtract the smallest uncovered entry from every uncovered cell and add it at every doubly covered intersection; repeat.

The implementation later uses the equivalent primal–dual shortest augmenting-path view. It grows the assignment one row at a time, maintains row/column potentials, stores each unused column's minimum slack, and updates only the values needed to reveal the next tight edge. This is the route to the compact $O(n^3)$ code.

Worked Matrix Example

Use workers $A,B,C$ and tasks $1,2,3$ with the cost matrix below. Row reduction subtracts $9,6,6$. The second reduced column then has minimum $2$, so column reduction subtracts $2$ there.

Why does a zero assignment recover the original cost? The reductions subtracted $9+6+6+2=23$ from every complete assignment. The selected entries total $0$ after reduction, so their original total is $0+23=23$. Checking the other five permutations confirms none is cheaper.

When Zeros Conflict

Reduction does not always reveal a perfect zero matching immediately. In the reduced matrix below, rows $A$ and $B$ can initially use only column $1$. The maximum independent-zero matching has size $2$, and all zeros can be covered by column $1$ plus row $C$.

The smallest uncovered value is $\delta=2$. Subtract it from uncovered cells $(A,2),(A,3),(B,2),(B,3)$ and add it to the doubly covered intersection $(C,1)$. The new matrix is

which admits independent zeros such as $A\to1$, $B\to2$, $C\to3$. The adjustment creates useful tight edges without invalidating the current dual prices.

Why the Method Is Correct

1. Reductions preserve the winner

Subtracting $r_i$ from row $i$ and $s_j$ from column $j$ subtracts the same total $\sum_i r_i+\sum_j s_j$ from every perfect assignment, because each assignment selects every row and column exactly once. Relative costs therefore do not change.

2. Potentials provide a lower bound

Choose row potentials $u_i$ and column potentials $v_j$ satisfying $u_i+v_j\le c_{ij}$. For any assignment $\pi$,

The right-hand side is a lower bound on every feasible assignment. Reduced costs $c_{ij}-u_i-v_j$ are nonnegative; their zeros are exactly the tight edges.

3. A tight perfect matching closes the gap

If every selected edge is tight, its total cost equals the dual lower bound. A feasible solution that attains a universal lower bound must be optimal. The algorithm alternates between improving the matching on tight edges and adjusting potentials until such a perfect matching exists.

Implementation

def hungarian_algorithm(cost):
    """
    Minimize an n x n assignment matrix.
    Return (row_to_column, total_cost) using the primal-dual
    shortest-augmenting-path form of the Hungarian algorithm.
    """
    n = len(cost)
    if n == 0:
        return [], 0
    if any(len(row) != n for row in cost):
        raise ValueError("cost must be a square matrix")

    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>
#include <stdexcept>
using namespace std;

pair<vector<int>, long long> hungarianAlgorithm(const vector<vector<long long>>& cost) {
    int n = cost.size();
    if (n == 0) return {{}, 0};
    for (const auto& row : cost)
        if ((int)row.size() != n) throw invalid_argument("cost must be square");
    const long long INF = numeric_limits<long long>::max() / 4;
    vector<long long> u(n + 1), v(n + 1);
    vector<int> p(n + 1), way(n + 1);

    for (int i = 1; i <= n; i++) {
        p[0] = i;
        int j0 = 0;
        vector<long long> minv(n + 1, INF);
        vector<bool> used(n + 1, false);
        do {
            used[j0] = true;
            int i0 = p[j0], j1 = -1;
            long long delta = INF;
            for (int j = 1; j <= n; j++) {
                if (!used[j]) {
                    long long 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);
    long long 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<long long>> 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(long[][] cost, long[] totalCostOut) {
        int n = cost.length;
        if (n == 0) return new int[0];
        for (long[] row : cost)
            if (row.length != n) throw new IllegalArgumentException("cost must be square");
        long[] u = new long[n + 1], v = new long[n + 1];
        int[] p = new int[n + 1], way = new int[n + 1];
        long INF = Long.MAX_VALUE / 4;

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

            do {
                used[j0] = true;
                int i0 = p[j0], j1 = -1;
                long delta = INF;
                for (int j = 1; j <= n; j++) {
                    if (!used[j]) {
                        long 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];
        long 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) {
        long[][] cost = {{9, 11, 14}, {6, 15, 13}, {12, 13, 6}};
        long[] totalCost = new long[1];
        int[] assignment = solve(cost, totalCost);
        System.out.println("Total cost: " + totalCost[0]);  // 23
    }
}

The arrays mirror the proof:

• u and v are row and column potentials.
• minv[j] is the smallest known reduced-cost slack for reaching unused column j.
• way[j] remembers the alternating-path predecessor used to reconstruct an augmentation.
• p[j] stores the row currently matched to column j; column 0 is a sentinel that anchors the search.

Complexity

For each of $n$ rows, the augmenting search can visit $O(n)$ columns, and each visit scans up to $O(n)$ unused columns. Therefore:

The classroom cover-and-adjust matrix presentation can take $O(n^4)$ when its matching and covering work is implemented naively. The shortest-augmenting-path potential formulation in the code avoids rescanning the full matrix after every small adjustment and achieves the standard cubic bound.

Rectangular, Maximization, and Forbidden Assignments

Where Assignment Modeling Appears

• Workforce scheduling: assign people to shifts or jobs using travel time, preference, or qualification penalties.
• Resource allocation: map machines to jobs, vehicles to requests, or channels to users.
• Evaluation and label alignment: optimally align predicted clusters, components, or identities with reference labels.
• Data association: match observations across images, time steps, or sensor streams.

The one-to-one, additive objective is the key. If a task needs several workers, assignments interact through time, or costs depend on combinations of pairs, the model has moved beyond the classical linear assignment problem.

Common Pitfalls and a Reliable Checklist

Exercises

1. Trace: reproduce both reductions in the SVG and list all six original assignment totals.
2. Conflict: for the adjustment matrix, find a minimum line cover, apply $\delta=2$, and give two different perfect zero matchings in the result.
3. Certificate: recover row and column potentials for the worked example and verify that each selected edge is tight.
4. Maximization: transform rewards $[[8,7,6],[6,9,5],[7,8,9]]$ into costs and confirm the best total reward.
5. Rectangular case: model three workers and two tasks where leaving a worker unassigned costs $4$. Explain the dummy column before solving.
6. Testing: compare the Python output against brute force on random matrices up to $n=7$, checking the total rather than the exact assignment.

History and Takeaway

Harold Kuhn published the Hungarian method in 1955, naming it for the foundational work of Hungarian mathematicians Dénes Kőnig and Jenő Egerváry. James Munkres studied assignment and transportation algorithms in 1957, helping establish the method's strongly polynomial character. The original matrix-style method is commonly analyzed at $O(n^4)$; later augmenting-path refinements produced the $O(n^3)$ form implemented above.