Job assignment with NO cost, would Hungarian method work?

Question

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?

Answer 1

The Hungarian algorithm could be made to work here, but an algorithm for unweighted maximum bipartite matching like Hopcroft–Karp would be faster.

Answer 2

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

Answer 3

Dummy costs should do the trick. Assign a cost of 1 to any job they can do, and an infinite cost (if your system allows that) to jobs they can't. The Hungarian algorithm is designed to minimize the total cost across all tasks, so it'll figure things out naturally. There shouldn't be any need to account for what you think their job preferences are; that's the algorithm's job.

Answer 4

Hungarian algorithm will give you an answer, but do not use infinity costs, since you cannot compare (infinity + infinity) and infinity (unless you compare the costs yourself).

A: 1, 2, 3

B: 1

C: 1

The matrix form:

  1   2   3

A 1   2   3

B 1   inf inf

C 1   inf inf

How can your computer compare 1, inf, inf and 2, 1, inf?

Instead, use some cost that is so large that it will guarantee to be not assigned (and yes, be careful with overflowing).