Hungarian Algorithm

The Hungarian Algorithm (also known as the Kuhn-Munkres Algorithm) solves the minimum cost perfect matching problem in a bipartite graph with edge weights.

Problem Definition

• There are $n$ workers and $n$ jobs.
• $cost[i][j]$ = cost for worker $i$ to do job $j$.
• Find an assignment so that each worker does exactly one job and the total cost is minimized.

Implementation

$O(n^3)$ Version

class Hungarian {
    int n;
    vector<vector<long long>> cost;
    vector<long long> u, v;  // potentials
    vector<int> p, way;
public:
    Hungarian(int n) : n(n), cost(n, vector<long long>(n)), u(n+1), v(n+1), p(n+1), way(n+1) {}
    void setCost(int i, int j, long long c) {
        cost[i][j] = c;
    }
    pair<long long, vector<int>> solve() {
        for (int i = 1; i <= n; i++) {
            p[0] = i;
            int j0 = 0;
            vector<long long> minv(n + 1, LLONG_MAX);
            vector<bool> used(n + 1, false);
            do {
                used[j0] = true;
                int i0 = p[j0], j1 = 0;
                long long delta = LLONG_MAX;
                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);
            do {
                int j1 = way[j0];
                p[j0] = p[j1];
                j0 = j1;
            } while (j0);
        }
        vector<int> assignment(n);
        for (int j = 1; j <= n; j++) {
            if (p[j] != 0) {
                assignment[p[j] - 1] = j - 1;
            }
        }
        long long totalCost = 0;
        for (int i = 0; i < n; i++) {
            totalCost += cost[i][assignment[i]];
        }
        return {totalCost, assignment};
    }
};

Example Usage

int n = 3;
vector<vector<long long>> cost = {
    {9, 2, 7},
    {6, 4, 3},
    {5, 8, 1}
};
Hungarian hungarian(n);
for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        hungarian.setCost(i, j, cost[i][j]);
    }
}
auto [minCost, assignment] = hungarian.solve();
cout << "Minimum cost: " << minCost << endl;
for (int i = 0; i < n; i++) {
    cout << "Worker " << i << " -> Job " << assignment[i] << endl;
}

Key Concepts

Dual Problem (Potentials)

Potentials $u_i$ (for workers) and $v_j$ (for jobs) must satisfy:

$u_i + v_j \leq cost[i][j]$

Optimality: $u_i + v_j = cost[i][j]$ for matched pairs.

Algorithm Steps

1. Initialize $u$ and $v$ to 0.
2. For each worker $i$:
   • Find an augmenting path in the equality graph.
   • If not possible, update potentials by $\delta = \min(cost[i][j] - u_i - v_j)$ for reachable $i$ and unreachable $j$.
   • Repeat until an augmenting path is found.
3. Augment the matching.

Variants

• Maximum Weight Matching: Negate costs or subtract from a large constant.
• Rectangular Matrix: Add dummy rows/columns with cost 0.

Applications

• Task assignment
• Object tracking across frames
• Resource allocation
• Minimum weight vertex cover in bipartite graphs

Complexity

Operation	Time	Space
Build	$O(n^2)$	$O(n^2)$
Solve	$O(n^3)$	$O(n^2)$

Comparison with MCMF

Aspect	Hungarian	MCMF
Time	$O(n^3)$	$O(n^2 E)$ (or better)
Use case	Dense bipartite	General flow
Implementation	Simpler	More general
Memory	$O(n^2)$	$O(V + E)$

Tips

1. Use Hungarian for dense graphs, MCMF for sparse graphs.
2. For large costs, be careful with overflow in potentials.
3. For floating point costs, handle precision carefully.