4
$\begingroup$

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.

$\endgroup$
5
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

Let $\mathrm{M}$ be a maximum matching in the equality subgraph. According to König's theorem, we can find a vertex cover $C$ such that $\mathrm{|M|}=|C|$. We Call $R$ the set $C\cap X$, and $T$ the set $C\cap Y$. Now, either $\mathrm{M}$ is a perfect matching, which means the algorithm should stop and return our current labelling as optimal, or $X$ is not saturated by $\mathrm{M}$. In that case, we adjust the weighted cover : We define $\epsilon = \min\{(u_i+v_j-w(x_iy_j):x_i\notin R, y_j \notin T\}$, and we substract $\epsilon$ to $u_i$ for each $x_i \notin R$, and we add $\epsilon$ to each $y_j$ for each $y_j \in T$. The cost of the cover changes by $(|T| - |X\setminus R|)\epsilon$. This change is strictly negative because $|R|+|T|=|\mathrm{M}|\lt |X| \Rightarrow |T| \lt |X|-|R| \Rightarrow |T| \lt |X \setminus R|$. Since we assumed the integrality of the labels, it ensures that the algorithm terminates in finitely many steps.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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