Linear Programming Duality & Complementary Slackness
The Assignment Problem seeks a permutation $\pi$ of $\{1, \dots, N\}$ minimizing $\sum_{i=1}^N C[i][\pi(i)]$. Consider any dual vertex potentials $u[1..N]$ and $v[1..N]$ satisfying the dual feasibility invariant:
$$u[i] + v[j] \le C[i][j] \quad \forall i, j \in \{1, \dots, N\}$$Define the slack of edge $(i, j)$ as $\text{slack}(i, j) = C[i][j] - u[i] - v[j] \ge 0$. For any valid permutation $\pi$, summing the dual inequality over all matched pairs $(i, \pi(i))$ gives:
$$\sum_{i=1}^N C[i][\pi(i)] \ge \sum_{i=1}^N \big(u[i] + v[\pi(i)]\big) = \sum_{i=1}^N u[i] + \sum_{j=1}^N v[j]$$Theorem (Complementary Slackness): If a perfect matching $M$ uses exclusively tight edges ($\text{slack}(i, j) = C[i][j] - u[i] - v[j] = 0$ for all $(i, j) \in M$), then $\text{cost}(M) = \sum u[i] + \sum v[j]$, so $M$ is a globally minimum-cost perfect matching.
Why $O(N^3)$ Instead of $O(N^4)$? When matching worker $i$ ($1 \le i \le N$), we grow an alternating tree $T$ of tight edges. Whenever $T$ cannot expand to an unmatched task, we compute the minimum slack $\Delta = \min_{i' \in T_L, j' \notin T_R} (C[i'][j'] - u[i'] - v[j'])$, add $+\Delta$ to $u[i']$ for $i' \in T_L$, and subtract $-\Delta$ from $v[j']$ for $j' \in T_R$. By maintaining an array minv[j] $= \min_{i' \in T_L} \text{slack}(i', j)$ for each column $j \notin T_R$, each of the $\le N$ tree expansions per worker takes $O(N)$ time, giving $O(N^2)$ per worker and $O(N^3)$ total!
Model Max-Weight Closure (Project Selection) as S-T Min-Cut with ∞ prerequisite arcs, tighten Hungarian dual potentials u_i + v_j = c_ij on the equality subgraph, or route Min-Cost Max-Flow via Johnson reduced costs.
Invariant & State
Rather than building graph objects, the industry-standard 1-indexed array formulation (Jonker & Volgenant 1987) uses Column $0$ as a virtual root holding the current worker $i$, and updates four flat 1D vectors (u, v, p, minv, way) in a tight inner loop over $j \in [1..M]$. Because it executes pure sequential array arithmetic with zero heap allocations, it solves $N = 500$ assignment instances in under $4\text{ ms}$!
| Algorithm Variant | Time Complexity | Space Complexity | Notes |
|---|---|---|---|
| Naive Kuhn-Munkres (Matrix Re-scan) | $O(N^4)$ | $O(N^2)$ | Recomputes $\Delta$ over all $(i', j')$ in $O(N^2)$ per relabel |
Hungarian with minv[j] Slack Array | $O(N^3)$ | $O(N^2)$ | Optimal for dense $N \times M$ assignment ($N \le M \le 1000$) |
| Rectangular $N \times M$ ($N \le M$) | $O(N^2 M)$ | $O(N M)$ | Matches every row $1..N$ to a distinct column in $1..M$ |
Production C++20 Implementation: $O(N^2 M)$ Hungarian Algorithm with Potentials
#include <vector>
#include <limits>
struct AssignmentResult {
long long minCost;
std::vector<int> rowMatch; // 0-indexed: rowMatch[i] = assigned column j
};
// Solves Min-Weight Matching matching all N rows to M columns (requires N <= M)
AssignmentResult hungarianMinWeightAssignment(const std::vector<std::vector<long long>>& cost) {
int n = static_cast<int>(cost.size());
int m = static_cast<int>(cost[0].size());
constexpr long long INF = std::numeric_limits<long long>::max() / 4;
// 1-indexed potentials u[1..n], v[0..m], matching p[0..m] (row matched to col j), way[1..m]
std::vector<long long> u(n + 1, 0), v(m + 1, 0);
std::vector<int> p(m + 1, 0), way(m + 1, 0);
for (int i = 1; i <= n; ++i) {
p[0] = i;
int j0 = 0;
std::vector<long long> minv(m + 1, INF);
std::vector<uint8_t> used(m + 1, 0);
do {
used[j0] = 1;
int i0 = p[j0], j1 = 0;
long long delta = INF;
for (int j = 1; j <= m; ++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 <= m; ++j) {
if (used[j]) {
u[p[j]] += delta;
v[j] -= delta;
} else {
minv[j] -= delta;
}
}
j0 = j1;
} while (p[j0] != 0);
// Augment matching along tight alternating path traced by way[]
do {
int j1 = way[j0];
p[j0] = p[j1];
j0 = j1;
} while (j0 != 0);
}
std::vector<int> rowMatch(n, -1);
for (int j = 1; j <= m; ++j) {
if (p[j] > 0) rowMatch[p[j] - 1] = j - 1;
}
// Dual objective at column 0: -v[0] equals sum u[i] + sum v[j] = exact minimum cost
return {-v[0], rowMatch};
}The 1-indexed Hungarian loop assumes every row $i \in [1..N]$ can be matched to a distinct column, which requires $N \le M$ (if $N > M$, transpose the matrix first!). To solve Maximum-Weight Matching, simply negate all matrix entries (cost[i][j] = -profit[i][j])—unlike Dijkstra, the Hungarian algorithm handles negative edge weights natively without offset hacks!