Consider the Hungarian Search algorithm for max/min weighted bipartite matching. Let G be a bipartite graph weighted by $w:E\rightarrow\mathbb{R}$ and let $M$ be a matching in $G$, let $S$ be a subset of edges of $G$. The net-cost of $S$ w.r.t. $M$ is defined as

$w_M(S):=\sum_{e\in S\setminus M} w(e) -\sum_{e\in S\cap M} w(e)$.

How would you prove or justify the claim that the Hungarian Search, with classical $\pm \delta$ dual-adjustments, augments $M$ by growing augmenting paths of minimum net-cost? Maybe we can think about the problem of finding an augmenting path as a max-flow augmenting step, with matched edges in one direction and unmatched undges the other way... ?


Your Answer

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

Browse other questions tagged or ask your own question.