algorithmhungarian-algorithm

Job assignment with NO cost, would Hungarian method work?


So I have a job assignment problem that doesn't have the traditional cost the Hungarian method requires.

For example:

I have 3 workers - A, B and C
I have 5 jobs -  1, 2, 3, 4 and 5

Each worker has a list of jobs he can perform, like so:

worker A can work on job 1, 2, 5
worker B can work on job 1, 2
worker C can work on job 1

The end result (since there's no cost) is the maximum number of assignments I can achieve. In this example, I can achieve a maximum of 3 assignments:

worker A on job 5
worker B on job 2
worker C on job 1

Is the Hungarian method a good way to solve this? Should I just use "dummy" costs? I was thinking maybe using the index of the job preference as the cost; is this a good idea?


Solution

  • Assign the cost -1 to the job which they can, and the others is zero.

    Then run the Hungarian algorithm and it will give you the answer(It will returns -answer,in fact).

    Don't do it with some large numbers, it may cause overflow(unless you implement the Hungarian very carefully).

    Indeed, it's Maximum matchings in bipartite graphs, and there are so many ways to solve this problem, see wiki pages:

    http://en.wikipedia.org/wiki/Matching_(graph_theory)#Maximum_matchings_in_bipartite_graphs

    PS:Hopcroft–Karp algorithm is faster than hungarian and is more simple also. It worth a try. Some compulicated method is faster than these two, but it's not recommanded to learn these algorithms at very first.

    PSS: Your ID in stackoverflow is a method to solve this problem. It's a network flow way. It's called shortest argument path(sap). See:http://coral.ie.lehigh.edu/~ted/files/ie411/lectures/Lecture11.pdf