Why my Hungarian Algorithm isn't working in specific cases?

Question

I am appling the Hungarian Algorithm to the following matrix:

\begin{bmatrix}0&0&0\\0&83&58\\0&72&10\end{bmatrix}

Following the steps:

1. Tick all unassigned rows

2. Tick all (unticked) columns that have zeros in ticked rows

3. Tick all (unticked) rows that have assigned zeros in ticked columns

4. Go back to point 2 unless there are no more columns that need ticking

5. Draw a line through every ticked column and every unticked row.

I end up having three lines to cover the zeros, while two lines would be sufficient, and this create problems in finding the final solution.

What am I doing wrong?

Thanks

Answer 1

I don't know from where comes your algorithm, but it is wrong. But more weirdly, the algorithm described on wikipedia is also wrong (and your version is probably adapted from it). For a correct description, you should rely on the original paper :

Munkres, James, Algorithms for the assigment and transportation problems, J. Soc. Ind. Appl. Math. 5, 32-38 (1957). ZBL0083.15302.

I think this link also have a correct description, if the paper seems to dry for you.

Applied on you matrix, here is what the algorithm should do : \begin{bmatrix}0&0&0\\0&83&58\\0&72&10\end{bmatrix} Star zeros greedily : \begin{bmatrix}0^*&0&0\\0&83&58\\0&72&10\end{bmatrix} Here, we star the first zero. No other zero can be starred, because every other zero is on the same row or column than an other starred zero.

Cover lines having starred zeros : \begin{bmatrix}X&&&\\0^*&0&0&\\0&83&58&\\0&72&10&\end{bmatrix}

Find a noncovered zero and prime it : \begin{bmatrix}X&&&\\0^*&0'&0&\\0&83&58&\\0&72&10&\end{bmatrix}

There is already a starred zero on the same line, so we cover the row, and uncover the row of the starred zero: \begin{bmatrix}&&&\\0^*&0'&0&X\\0&83&58&\\0&72&10&\end{bmatrix}

Find a noncovered zero and prime it : \begin{bmatrix}&&&\\0^*&0'&0&X\\0'&83&58&\\0&72&10&\end{bmatrix}

There is no starred zero on the same line, so we find a starred zero on the same column, then a primed zero on the same row as the starred zero, and repeat. We go on like this until we find a primed zero whic his not on the same column as a starred zero. (This should not be possible to end on a starred zero which have no primed zero on the same line). \begin{bmatrix}&&&\\(0^*)&(0')&0&X\\(0')&83&58&\\0&72&10&\end{bmatrix}

We unstar the found starred zeros, and star the found primed zeros, and remove everything else (covers and primed zeros, except already starred zero). We now have one more starred zero, so it is an improvment : \begin{bmatrix}&&&\\0&0^*&0&\\0^*&83&58&\\0&72&10&\end{bmatrix}

We do the same thing over again. We cover column of starred zeros : \begin{bmatrix}X&X&&\\0&0^*&0&\\0^*&83&58&\\0&72&10&\end{bmatrix}

Find a noncovered zero and prime it : \begin{bmatrix}X&X&&\\0&0^*&0'&\\0^*&83&58&\\0&72&10&\end{bmatrix}

There is already a starred zero on the same line, so we cover the row, and uncover the row of the starred zero: \begin{bmatrix}X&&&\\0&0^*&0'&X\\0^*&83&58&\\0&72&10&\end{bmatrix}

Every zero is covered, so we stop, starred zeros are the optimal assignment of zeros.