2
$\begingroup$

When I look online for examples of the Hungarian method for solving the min-weight assignment problem, for example here, it involves iterating on the cost matrix; subtracting entries from the rows and columns.

However, in section 17.2 of the book, Combinatorial optimization polyhedra and efficiency by Schrijver, a seemingly different algorithm is presented. Here, we start with a matching $M$, assign $W_M$ and $U_M$ as the edges on the left and right of the bi-partite graph that haven't been covered by the matching, describe path lengths as $l_e=w_e$ if the edge is in $M$ and $l_e=-w_e$ otherwise and find a min path from $U_M$ to $W_M$. Then, reset $M$ to $M'$, the symmetric difference between the path $P$ and $M$.

These two algorithms seem very different to me. Are they somehow the same under the cover?

$\endgroup$

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.