Allocate Algorithm/Availability Algorithm

Question

I am wondering if anyone knows of an Algorithm I could use to help me solve the following problem:

Allocate people (n) to certain events (m), m can have only one person attached to it and it must be randomized each time (Same person allowed if only one option available(n)). n has properties such as time available and day available. For n to be matched to m the time available and day available must match for both n and m. There can be multiple of n that match the times of m but it has to be the best fit so the rest of m can be allocated. The diagram below will more than likely explain it better (Sorry). n can be allocated to more than one m but should be done fairly such that one n doesnt have all of the available m's

As you can see Person A could be attached to Event A but due to the need to have them all matching (the best attempt to match) it is attached to Event B to allow Person C to be allocated to Event A and person B to Event C.

I am simply wondering if anyone knows the name of this type of problem and how I could go about solving it, I am coding the program in Java

Answer 1

This is a variant of the the Max Flow Problem. There are many algorithms taylor-made to solve max-flow problems, including The Ford-Fulkerson Algorithm or its refinement, the Edmonds-Karp Algorithm. Once you are able to change your problem into a max-flow problem, solving it is fairly simple. But what is the max flow problem?

The problem takes in a weighted, directed graph and asks the question "What is the maximum amount of flow that can be directed from the source (a node) to the sink (another node)?". There are a few constraints, that make logical sense when thinking of the graph as a network of water flows.

1. The amount of flow through each edge must be less than or equal to the "capacity" (weight) of that edge for every edge in the graph. They also must be non-negative numbers.
2. The amount of flow into each node must equal the amount of flow leaving that node for ever node except the source and sink. There is no limit to the amount of flow that goes through a node.

Consider the following graph, with s as the source and t as the sink.

The solution to the max flow problem would be a total flow of 25, with the following flow amounts:

It is simple to transform your problem into a max flow problem. Assuming your inputs are:

• N people, plus associated information on when person p_i is available time and date wise.
• M events with a time and place.

Create a graph with the following properties:

• A super source s
• N person nodes p_1 ... p_n, with an edge of capacity infinity connecting s to p_i for all i in 1 ... n.
• A super sink t
• M event nodes e_1 ... e_m, with an edge of capacity 1 connecting e_i to t for all i in 1 ... m
• For every combination of a person and event (p_i, e_j), an edge with capacity infinity connecting p_i to e_j iff p can validly attend event e (otherwise no edge connecting p_i and e_j).

Constructing a graph to these specifications has O(1) + O(N) + O(N) + O(M) + O(M) + O(1) + O(NM) = O(NM) runtime.

For your example the constructed graph would look like the following (with unlabeled edges having capacity infinity):

You correctly noticed that there is a Max Flow with value 4 for this example, and any max flow would return the same value. Once you can perform this transformation, you can run any max flow algorithm and solve your problem.