CODEWITHSUNDEEP
algorithm
Lee Daniel Crocker
Lee Daniel Crocker

Reputation: 13171

Hungarian (Kuhn Munkres) algorithm oddity

I've read every answer here, Wikipedia and WikiHow, the indian guy's lecture, and other sources, and I'm pretty sure I understand what they're saying and have implemented it that way. But I'm confused about a statement that all of these explanations make that is clearly false.

They all say to cover the zeros in the matrix with a minimum number of lines, and if that is equal to N (that is, there's a zero in every row and every column), then there's a zero solution and we're done. But then I found this:

    a  b  c  d  e

A   0  7  0  0  0
B   0  8  0  0  6 
C   5  0  7  3  4 
D   5  0  5  9  3 
E   0  4  0  0  9

There's a zero in every row and column, and no way to cover the zeros with fewer than five lines, but there's clearly no zero solution. Row C has only the zero in column b, but that leaves no zero for row D.

Do I misunderstand something here? Do I need a better test for whether or not there's a zero assignment possible? Are all these sources leaving out something essential?

Upvotes: 3

Views: 1995

Answers (1)

svk
svk

Reputation: 5919

You can cover the zeros in the matrix in your example with only four lines: column b, row A, row B, row E.

Here is a step-by-step walkthrough of the algorithm as it is presented in the Wikipedia article as of June 25 applied to your example:

    a  b  c  d  e

A   0  7  0  0  0
B   0  8  0  0  6 
C   5  0  7  3  4 
D   5  0  5  9  3 
E   0  4  0  0  9

Step 1: The minimum in each row is zero, so the subtraction has no effect. We try to assign tasks such that every task is performed at zero cost, but this turns out to be impossible. Proceed to next step.

Step 2: The minimum in each column is also zero, so this step also has no effect. Proceed to next step.

Step 3: We locate a minimal number of lines to cover up all the zeros. We find [b,A,B,E].

    a  b  c  d  e

A   ---|---------
B   ---|---------
C   5  |  7  3  4 
D   5  |  5  9  3 
E   ---|---------

Step 4: We locate the minimal uncovered element. This is 3, at (C,d) and (D,e). We subtract 3 from every unmarked element and add 3 to every element covered by two lines:

    a  b   c  d  e

A   0  10  0  0  0
B   0  11  0  0  6 
C   2  0   4  0  1 
D   2  0   2  6  0 
E   0  7   0  0  9

Immediately the minimum number of lines to cover up all the zeros becomes 5. This is easy to verify as there is a zero in every row and a zero in every column. The algorithm asserts that an assignment like the one we were looking for in step 1 should now be possible on the new matrix.

We try to assign tasks such that every task is performed at zero cost (according to the new matrix). This is now possible. We find the solution [(A,e),(B,c),(C,d),(D,b),(E,a)].

We can now go back and verify that the solution that we found actually is optimal. We see that every assigned job has zero cost, except (C,d), which has cost 3. Since 3 is actually the lowest nonzero element in the matrix, and we have seen that there is no zero-cost solution, it is clear that this is an optimal solution.

Upvotes: 8

Related Questions