viii. Assignment Problem

Assign $n$ workers to distinct jobs among $m\ge n$ minimising $\sum c_{i\sigma (i)}$: a minimum-cost perfect matching in a complete bipartite graph. It hides behind “pick one entry per row in distinct columns”, “pair red and blue points minimising total distance”, “schedule tasks to machines with costs”. Greedy is wrong (\begin{psmallmatrix}1&2\\4&100\end{psmallmatrix}: greedy 101, optimum 6).

Method	Time	$n$
bitmask DP over used jobs	$O(2^{n}n)$	$\le 20$
Hungarian (Kuhn–Munkres, JV-style)	$O(n^{2}m)$	$\le 1000$–$3000$
min-cost flow (SSP)	$O(n\cdot E\log V)$	sparse graphs
auction, Gabow–Tarjan scaling	$O(\sqrt{n}m\log (nC))$	theory

Hungarian algorithm

Maintain potentials $u_i,v_j$ with $u_i+v_j\le c_{ij}$ and add rows one at a time: each row runs a Dijkstra on reduced costs over columns, shifting potentials by the minimum slack until an unmatched column is reached, then flips the alternating path.

pair<ll, vector<int>> hungarian(const vector<vector<ll>>& a) {   // n rows <= m columns; {min cost, row -> column}
    if (a.empty()) return {0, {}};
    int n = sz(a) + 1, m = sz(a[0]) + 1;
    vector<ll> u(n), v(m); vector<int> p(m), ans(n - 1);   // p[j]: row matched to column j (0 = none)
    for (int i = 1; i < n; i++) {
        p[0] = i; int j0 = 0;                               // column 0 is a dummy holding the new row
        vector<ll> dist(m, LLONG_MAX); vector<int> pre(m, -1); vector<char> done(m + 1);
        do {
            done[j0] = 1; int i0 = p[j0], j1 = 0; ll delta = LLONG_MAX;
            for (int j = 1; j < m; j++) if (!done[j]) {
                ll cur = a[i0 - 1][j - 1] - u[i0] - v[j];
                if (cur < dist[j]) dist[j] = cur, pre[j] = j0;
                if (dist[j] < delta) delta = dist[j], j1 = j;
            }
            for (int j = 0; j < m; j++) if (done[j]) u[p[j]] += delta, v[j] -= delta; else dist[j] -= delta;
            j0 = j1;
        } while (p[j0]);
        while (j0) { int j1 = pre[j0]; p[j0] = p[j1], j0 = j1; }
    }
    for (int j = 1; j < m; j++) if (p[j]) ans[p[j] - 1] = j - 1;
    return {-v[0], ans};
}

• Maximise: negate the matrix. Forbidden pairs: a large cost (check the answer against it).
• Maximum-weight matching, not necessarily perfect, with $w\ge 0$: pad to a square matrix with 0 for absent pairs and maximise.
• The potentials are an optimality certificate: $\sum u+\sum v$ equals the answer, and the same dual-potential idea reappears in min-cost flow’s successive-shortest-paths and in Johnson’s reweighting — understanding it once pays off repeatedly.
• $k$ best assignments: Murty’s partitioning (fix / forbid one pair at a time from the best solution), $k$ Hungarian runs per output.

Proof: Hungarian is optimal and $O(n^{2}m)$

Dual feasibility $u_i+v_j\le c_{ij}$ is maintained for the rows inserted so far (negative costs are fine). A new row $i$ starts with $u_i=0$; the first step of its phase has only the dummy column in the tree, computes $\delta ={\min }_j(c_{ij}-v_j)$ (possibly negative) and shifts $u_i$ by $\delta$, after which all of row $i$‘s constraints hold with the minimiser tight. From then on every slack is $\ge 0$, so $\delta \ge 0$. Updates: for tree rows and tree columns both shifted, $u+v$ is unchanged; tree row with non-tree column loses exactly $\delta \le$ its slack ($\delta$ is the minimum slack dist); non-tree row with tree column gains slack. So feasibility is kept and the edge achieving $\delta$ becomes tight. Matched edges stay tight. Each step adds one column to the tree, so a phase has $\le m$ steps of $O(m)$ work, and $n$ phases give $O(n^{2}m)$.

Optimality: columns enter the tree only during a phase, and every tree column is matched at its end, so columns with $v_j\ne 0$ are matched and $v_j\le 0$ always (columns only decrease). At the end, matched edges are tight: cost $={\sum }_i{u}_i+{\sum }_{\text{matched }j}{v}_j={\sum }_i{u}_i+{\sum }_j{v}_j$. For any assignment $\sigma$, ${\sum }_i{c}_{i\sigma (i)}\ge {\sum }_i{u}_i+{\sum }_i{v}_{\sigma (i)}\ge {\sum }_i{u}_i+{\sum }_j{v}_j$ (the extra $v_j\le 0$ only lower the right side). So the matching is optimal. The returned value: every step raises $\sum u+{\sum }_{j\ge 1}v$ by exactly $\delta$ (one more tree row than tree columns $\ge 1$, because of the dummy column 0) and lowers $v_0$ by $\delta$, so $-v_0$ equals the dual objective, which is the cost.

Small $n$: bitmask DP

ll assignmentDP(const vector<vector<ll>>& c) {              // n rows <= m columns, m <= ~20
    int n = sz(c), m = sz(c[0]); vector<ll> dp(1 << m, LLONG_MAX); dp[0] = 0; ll best = LLONG_MAX;
    for (int mask = 0; mask < (1 << m); mask++) {
        if (dp[mask] == LLONG_MAX) continue;
        int i = __builtin_popcount(mask);                   // the next row to assign
        if (i == n) { best = min(best, dp[mask]); continue; }
        for (int j = 0; j < m; j++) if (!(mask >> j & 1)) dp[mask | 1 << j] = min(dp[mask | 1 << j], dp[mask] + c[i][j]);
    }
    return best;
}

Special structure

• Monge / convex costs on a line: if $c_{ij}=f(x_i-y_j)$ with $f$ convex (e.g. $|x-y|$, $(x-y{)}^2$), sorting both sides and matching in order is optimal; with $m>n$ it becomes a DP $dp[i][j]$ over sorted lists in $O(nm)$ (or slope trick).
• Bottleneck assignment (minimise the maximum cost): binary search a threshold and test for a perfect matching with Hopcroft–Karp.
• Points in the plane, Euclidean costs: still Hungarian in general; Manhattan distance on a line is the sorted case.
• 3-dimensional assignment is NP-hard.
• Workers can take up to $k$ jobs each (generalised/transportation assignment, unequal supply and demand): drop Hungarian for min-cost flow with capacities $k$ on the worker side.
• Costs change between queries: either rerun Hungarian from scratch, or maintain the dual potentials and re-augment incrementally from the changed rows/columns only.
• Non-bipartite (match within one set, not between two): this is weighted general matching, not assignment — see General Matching (weighted Blossom).

Proof: sorted matching for convex $f(x-y)$

For $x_1\le x_2$ and $y_1\le y_2$, put $a=x_1-y_2\le$ both $x_1-y_1$ and $x_2-y_2$ $\le x_2-y_1=b$, and $(x_1-y_1)+(x_2-y_2)=a+b$. Convexity of $f$ gives $f(x_1-y_1)+f(x_2-y_2)\le f(a)+f(b)$ (the pair closer to the middle has the smaller sum). So un-crossing any inverted pair of an assignment does not increase the cost, and repeatedly doing so reaches the sorted assignment.