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?


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.