Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

In reading the proof of the Hungarian algorithm for the assignment problem in a weighted bigraph, I could not understand why the algorithm terminates. In the algorithm we choose a cover (namely labels for the vertices of the bigraph: $u_1\cdots u_n$, $v_1,\cdots v_n$ with $u_i+v_j\ge $weight of an edge $x_iy_j\forall i,j$) and keep adjusting it until the equality subgraph (the spanning subgraph of $K_{n,n}$ whose edges are pairs $x_iy_j$ such that $u_i+v_j=$weight of $x_iy_j$) has a perfect matching. My question is after each adjustment, why does the cost of the cover $\sum(u_i+v_i)$ reduce?

(We assume the weights are all integers).

Thanks.

share|improve this question
add comment

1 Answer

up vote 4 down vote accepted

Let the two sets of vertices be $X$ and $Y$. If the equality subgraph does not have a perfect matching, it must violate Hall’s marriage condition, so there is some $X'\subseteq X$ adjacent to fewer than $|X'|$ vertices in $Y$. Let $Y'$ be the set of vertices in $Y$ adjacent to $X'$ in the equality subgraph. The adjustment to the cover consists in replacing $u_k$ by $u_k-\alpha$ for each $x_k\in X'$ and $v_k$ by $v_k+\alpha$ for each $y_k\in Y'$, where $\alpha=\min\{u_k+v_j-\operatorname{wt}(x_ky_j):u_k\in X'\text{ and }y_j\in Y'\}$. The net change in the cost of the cover is therefore $\left(-|U'|+|V'|\right)\alpha<0$, and the cost of the new cover is therefore less than the cost of the old.

This PDF has a presentation that I think is slightly different from the one that you have in mind; it arrives at the optimality by a different route that may be easier to follow, especially with the nice example at the end.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.