Eq. (3.4) — the assignment dual w(π) is the minimum of c_A + π·v_A over all n^n assignments

Let $A=(a_{ir})$ be a real $n\times n$ cost matrix ($a_{ir}$ = cost of man $i$ on job $r$), and let $w$ be the dual function (3.3), $w(\pi)=\sum_i\pi_i+\sum_r\min_s[a_{sr}-\pi_s]$. For an assignment $A:\{1,\dots,n\}\to\{1,\dots,n\}$ (job $r$ goes to man $A(r)$, not necessarily one-to-one) write $c_A=\sum_r a_{A(r)\,r}$ and $(v_A)_i=1-\#\{r:A(r)=i\}$. Then for every $\pi\in\mathbb R^n$,

the minimum being over all $K=n^n$ assignments.

This exhibits $w$ in the form (2.2) of the paper, $w(\pi)=\min_k\{c_k+\pi\cdot v_k\}$, so that the general subgradient method of Section 2 applies to the assignment dual, with $v_A$ a subgradient at $\pi$ whenever $A$ attains the minimum.

Formalization Note The minimum over the finite, nonempty type Fin n → Fin n is Finset.univ.inf' (nonemptiness witnessed by the identity), and $\pi\cdot v_A$ is written as the sum $\sum_i \pi_i (v_A)_i$.