Past exam of the Probability, statistics and options II course of the University of Oxford / 2007 / S / 4

For every perfect matching $M$, each vertex occurs exactly once, so the feasibility inequalities giveIf a perfect matching $M^{\ast }$ uses only tight edges, equality holds. It therefore attains a lower bound valid for every perfect matching, proving minimum cost. In a bipartite graph this is the weak duality and complementary slackness certificate for the assignment problem. The Hungarian algorithm maintains feasible row and column potentials and seeks a perfect matching among tight edges.

Begin with $u=v=0$ and the printed matching $\{(1,1),(3,2),(5,3)\}$. Grow an alternating tree from unmatched row two. Its tight edge reaches column two, whose matched row is three. Thus the reached row set is $S=\{2,3\}$ and the reached column set is $T=\{2\}$. Among unreached columns the reduced costs are $(6,5,4,4)$ from row two and $(3,4,2,3)$ from row three, so their minimum is two.

Increase $u_2,u_3$ by two and decrease $v_2$ by two. The new tight edge $(3,4)$ reaches an unmatched column. Augment along $2\to 2\to 3\to 4$, replacing $(3,2)$ by $(2,2),(3,4)$. The matching becomes $\{(1,1),(2,2),(3,4),(5,3)\}$.

Now grow from unmatched row four. Edge $(4,1)$ reaches matched row one, and edge $(1,5)$ reaches unmatched column five. Augment along $4\to 1\to 1\to 5$, replacing $(1,1)$ by $(4,1),(1,5)$. This yieldsNo further potential update is needed. The final potentials are $u=(0,2,2,0,0)$ and $v=(0,-2,0,0,0)$. Their reduced-cost matrix isEvery entry is nonnegative and every chosen entry is zero. The dual sum is $\sum u_i+\sum v_j=2$, so part (a) certifies optimality.

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 byAll feasibility inequalities remain valid by the definition of the minimum slack.