1
$\begingroup$

I have been having some difficulty making sense of the Hungarian Algorithm outlined here. It seems incomplete and/or erroneous to me. The main issue is the line:

If R_T ^ Z is nonempty, then reverse the orientation of a directed path in...

How do we know which path to select as "a path"? If we select the wrong path, how do we recover? This seems to be a monotonically assigning algorithm, in that we can only ever create new assignments, but never remove or alter existing ones.

Suppose we have a simple example of S = {A, B}, T = {W, X} with weights AW: 2, AX: 2, BW: 6, BX: 4. How do we select whether to add AW or AX to the mapping first, or how to we recover from making the wrong selection?

$\endgroup$
  • 1
    $\begingroup$ Any augmenting path serves. Note that you reverse the order of the arcs. Say you choose AW of cost 2 first. Then you have forward arcs AX, BW, BX, and backward arc WA, which has been reversed. Now BW,WA,AX is an augmenting path, of cost 6-2+2=6, and you end up with backward arcs WB,XA which represent the optimal solution 8. $\endgroup$ – Marcus Ritt May 1 at 0:50
  • $\begingroup$ Oh, I see, that's kind of obvious now that you mention it. But it didn't come to me reading that explanation. (They are discussing minimum cost, but it doesn't matter) $\endgroup$ – Apollys supports Monica May 1 at 0:56
2
$\begingroup$

(Converting a comment into a proper answer. Note that I now use the minimum cost convention of the reference given in the question.)

Any augmenting path serves. Note that you reverse the order of the arcs. Say you choose AW of cost -2 first. Then you have forward arcs AX, BW, BX, and backward arc WA, which has been reversed. Now BW,WA,AX is an augmenting path, of cost -6+2-2=-6, and you end up with backward arcs WB,XA which represent the optimal solution 8.

$\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.