Assignment Problem

Problem. $n$ workers, $n$ jobs, a cost matrix $c_{ij}$ . Assign each worker to exactly one job minimising the total cost.

Equivalently: a minimum-cost perfect matching in a complete bipartite graph.

The methods

Method	Time	Feasible $n$
Brute force over permutations	$O (n!)$	10
Bitmask DP	$O (2^{n} n)$	20
Hungarian algorithm	$O (n^{3})$	500-1000
Min-cost flow (SSP + potentials)	$O (n \cdot m lo g n)$	500
Gabow-Tarjan scaling	$O (n m lo g (n C))$	theoretical
Auction algorithm	$O (n^{3} lo g (n C))$	parallelisable
Greedy	$O (n^{2} lo g n)$	not optimal

Write the Hungarian algorithm for $n \geq 20$ , bitmask DP below that.

Bitmask DP — the easy option

long long assignment(int n, vector<vector<long long>>& c) {
    vector<long long> dp(1 << n, LLONG_MAX / 2);
    dp[0] = 0;
    for (int mask = 0; mask < (1 << n); mask++) {
        int i = __builtin_popcount(mask);                // next worker to assign
        if (i == n || dp[mask] == LLONG_MAX / 2) continue;
        for (int j = 0; j < n; j++)
            if (!(mask >> j & 1))
                dp[mask | (1 << j)] = min(dp[mask | (1 << j)], dp[mask] + c[i][j]);
    }
    return dp[(1 << n) - 1];
}

Using popcount(mask) to derive the worker index removes an entire dimension. $O (2^{n} n)$ — instant for $n \leq 20$ , and far easier to get right than Hungarian.

The Hungarian algorithm in one paragraph

Maintain dual potentials $u_{i}$ (workers) and $v_{j}$ (jobs) with $c_{ij} - u_{i} - v_{j} \geq 0$ . Edges achieving equality form the tight subgraph; grow an alternating tree in it, and when stuck, adjust the potentials by the minimum slack to expose new tight edges. Each of $n$ phases matches one more worker in $O (n^{2})$ , giving $O (n^{3})$ .

The invariant $c_{ij} \geq u_{i} + v_{j}$ is LP duality: at the end $\sum u_{i} + \sum v_{j}$ equals the optimum, which is a certificate of optimality. See Hungarian Algorithm.

Variants

Variant	Method
Maximise instead of minimise	negate the costs, or subtract from the maximum
Rectangular ( $n \neq = m$ )	pad with zero-cost dummy rows or columns
Some assignments forbidden	set those costs to $+ \infty$
Bottleneck assignment (minimise the max cost)	binary search + bipartite matching
Workers handle $k$ jobs	min-cost flow with capacities
Costs change over time	recompute, or use the incremental Hungarian
Non-bipartite (general graph)	weighted Blossom
Only feasibility (any perfect matching)	Hopcroft-Karp, $O (E V)$
3-dimensional assignment	NP-hard

Bottleneck assignment is worth calling out: binary search the threshold $X$ , keep only edges with cost $\leq X$ , and test for a perfect matching. $O (n^{2} n lo g C)$ and much simpler than a specialised algorithm — the standard “binary search + feasibility” pattern.

Why greedy fails

Assigning the globally cheapest pair, then the next, and so on, is not optimal:

$c = (142100)$

Greedy takes $(0, 0) = 1$ then is forced into $(1, 1) = 100$ , total 101. The optimum is $(0, 1) + (1, 0) = 2 + 4 = 6$ .

The failure is instructive: greedy has no way to account for the opportunity cost of a choice, which is exactly what the Hungarian algorithm’s dual potentials encode.

Recognising it

The assignment problem hides behind many phrasings:

“match each person to a task minimising total time”,
“pair up points to minimise total distance” (with two colour classes),
“assign each row a distinct column with minimum penalty”,
“select one element from each row, all in distinct columns”.

Whenever a problem needs a bijection between two sets of size $n$ with an additive cost, it is this problem.

Why it is worth knowing

It is the canonical example of a problem where:

the naive greedy is wrong,
the exponential search is unnecessary,
and a polynomial algorithm exists via LP duality.

The dual potentials also reappear in min-cost flow and Johnson’s reweighting, so understanding them once pays off repeatedly.

See also: Hungarian Algorithm · Min-Cost Flow · Bitmask DP

whoashish's cp notes

Directory