= Solution
Before a potential update, let $S$ be the reached rows and $T$ the reached columns in an alternating forest grown from unmatched rows. Every reached column is matched, or an augmentation would already have occurred, and its matched row is reached. Each <tree> has one more reached row than reached column, so $|S|-|T|>0$.
The update amount is the smallest slack across $S\times T^c$. It is strictly positive because all zero-slack <edges> have already been explored, and the complete <assignment problem> guarantees that the set is nonempty before a <perfect matching> is found. Increasing $u_i$ for $i\in S$ and decreasing $v_j$ for $j\in T$ therefore increases the dual sum by
$$
\boxed{\Delta(|S|-|T|)>0.}
$$
All feasibility inequalities remain valid by the definition of the minimum slack.
Back to article page
