Sufficient resources for N requesters and M resources

Question

This problem feels familiar, but I don't recall the solution (or whether it was any good).

Another way to put this would be, you have N potential matches, and M positions they could be in - each N can only fit in a subset of the M positions - are there sufficient positions for this configuration.

It's better demonstrated by a diagram. Setting N to 3 (along the top) and M to 4, using a 1 to indicate which resource (M) a requester (N) needs - Example situation where there would be insufficient resources:

   0  1  2
0  1  1  1
1  1  1  1
2  0  0  0
3  0  0  0

   0  1  2
0  1  X  X
1  X  1  X
2  0  0  0
3  0  0  0

Once 0 and 1 have been allocated, there is no resource left available in 2's subset. On the other hand, this situation would allow sufficient resource allocation.

   0  1  2
0  1  1  1
1  1  1  1
2  0  0  0
3  0  1  0

   0  1  2
0  1  X  X
1  X  X  1
2  0  0  0
3  0  1  0

I really only care about whether the allocation can be satisfied or not. Not necessarily the configuration that satisfies it.

If there is no simple way to get a yes or no, I was thinking of targeting the rows and columns with the least possibilities first. I think that would narrow it down quickly. As well, identifying unsatisfiable situations might be a good means of elimination.

My question to you, is there any math, a good algorithm, or a class of problems I should look at for this? It seems like something from real time programming or sodoku. Even just a term to google would be much appreciated.

Thanks!

Answer 1

I ended up using [Hall's Theorem][1] for this since there is no 'cost'.

Edit: I will end up using bipartite matching.

Answer 2

I believe you want to check the Assignment Problem (http://en.wikipedia.org/wiki/Assignment_problem)

One way to approach it is using the Hungarian Algorithm (http://en.wikipedia.org/wiki/Hungarian_algorithm)

And there are some libraries that already implement it, for instance: http://robotics.stanford.edu/~gerkey/tools/hungarian.html