Hungarian algorithm: I'm having trouble with assigning as many jobs to workers as possible

Question

I have created an implementation of the Hungarian algorithm in C++. This implementation works very well for many cases. However there are some cases that my algorithm does not work at all because I believe(and it's true) that my implementation of one step of the algorithm is wrong.

My implementation takes as an input the array X, runs the steps of the algorithm and produces the final assignment.

The steps of the algorithm can be found on wiki:Hungarian Algorithm

In step 3 it has the following array of costs(workers are represented by rows and jobs by columns)

and then it says

Initially assign as many tasks as possible then do the following 

However I don't understand what a correct implementation of this would be. How can you assign as many tasks as possible? Would the choice be random? Then if the choice would be random, I could choose the first worker to take the first job, the second worker to take the fourth job and the fourth worker to take the second job. So the second worker is left out. However in wikipedia the authors took a different approach. The third worker has to take the first job, the second worker has to take the second job and the fourth worker has to take the second job. So the first worker is left out.

The problem with doing such random actions is the following case:

Suppose while we run the algorithm and doing our arithmetic operations on the input, before assigning as many tasks to workers as possible we have the following cost matrix:

2 2 0 3
6 1 6 0
0 0 6 1
0 3 5 3

If I choose randomly to assign the third job to the first worker, the fourth job to the second worker and then the first job to the third worker, I will have the fourth worker left out. But for the algorithm to work correctly we need to assign as many jobs to workers as possible. Is this the case here? No, because if instead of assigning the first job to the third worker I assigned the first job to the fourth worker, I could then assign the second job to the third worker and thus the algorithm not only would assign as many jobs to workers as possible but it would find the optimum result.

Conclusion: Doing random assignments is not a good approach.

I searched about this a little bit and I found the following lecture:

http://www.youtube.com/watch?v=BUGIhEecipE

In this lecture the professor suggests a different approach for the problem of assigning as many tasks as possible. According to him if any row or column has exactly one zero, we will make an assignment. So starting from the first row you check to see if the first row has only one zero, if that's the case, make an assignment. Otherwise ignore that row and go to the second row, do the same thing repeatedly by rescanning the table until all the zeros are covered due to assignments.

By following this approach, one can see that the previous case is solved. What we do is, we assign the third job to the first worker, the fourth job to the second worker, then we see that the third worker can take 2 jobs so we ignore him for a while, we assign the first job to the fourth worker and then return in order to assign the second job to the third worker.

My implementation follows this logic, however again, it does not solve all the cases.

Let's take for example the following case:

0 0 0 0
0 0 0 0
0 0 4 9
0 0 2 3

The first worker can take 4 jobs, the second 4, the third 2 and the fourth 2. So my implementation does no assignments, because I would need at least one worker who can only take one job in order to do an assignment and then continue by re scanning the table. So what do I do in this case? Arbitrary assignments would be a bad thing to do, unfortunately nothing is suggested in that lecture. I could only think of the following:

For each worker have a counter whose value indicates the amount of tasks that can be assigned to him, so how many zeros do we have in that row? that's the value of the counter. Then start assigning arbitrary tasks to the worker with the smallest counter. So in this case, the array of counters for each workers would include the following values:

4
4
2
2

I would choose for example the third worker and arbitrary assign to him the first job. The new counters would be:

3
3
0
1

I would then choose the fourth worker and do the only assignment available for him(which is the second job). The new counters would be:

2
2
0
0

Then I could choose either the first worker or the second. I would do an arbitrary assignment for the first worker and give him the third job. The counters would be

1
0
0
0

Finally I would give the fourth assignment to the first job.

So the final assignments:

0 0 0 *
0 0 * 0
* 0 4 9
0 * 2 3

It seems like a good approach, however I'm afraid there might be a special case that this method would not work. How can I verify whether this approach would work for all cases, and if it won't, what approach would solve my problem completely?

Thank you in advance

Answer 1

Your current approach does not work.

0 2 0
3 0 0
4 0 0

Your method: " Then start assigning arbitrary tasks to the worker with the smallest counter. " All workers have the same counter, so say you pick worker 1 and assign him to task 3, you can only match one of the remaining workers, while with this matrix you could obviously match all three.

What you need is a maximum bipartite matching between those workers and tasks, where a pair is matchable if there is a 0 in the relevant position. Such a matching can be found by manually going through augmenting paths or more quickly by using the Hopcroft-Karp algorithm.