Scheduling classes with lower and upper bounds on students and classes

Question

I am struggling to solve the following excercise:

Design an assignment of a group of n students to m classes. Student i should take a minimum of $l_i$, and a maximum of $u_i$ within a set C1 of classes. Class j should be attended by a minimum of $m_j$ and a maximum of $M_j$ students in order to be activated.

1. Design an algorithm that solves the problem of the existence of a feasible schedule in polynomial time.
2. Study the time complexity of the algorithm.

I think I am overthinking this a bit: I have tried creating a graph made as follows:

• Minimum classes per student as capacities on edges from a source to each student
• Maximum number of students per class on edges from classes to a sink
• Edges between students and classes: if student $i$ can attend class $j$, then there is a single capacity edge This was done in order to calculate max-flow, which I am aware would not actually solve the problem. But I can't come up with anything better. Any help would be greatly appreciated!

Answer 1

I think you are almost there: the intuition about using the max-flow is correct.

In your graph model one thing lacking is the constraint on minimum students that a class must have(for this to be a feasible solution).

A correct model(on which an appropriate max flow algorithm would give us the answer on existence of solution) is:

• Create node sink t and source s.
• Create a node for each student and a node for each class.
• From node s create an arc to each student node with maximum capacity equal to the maximum number of classes the student can take and minimum capacity as the number of classes the student must take.
• Each student node has an arc to each class node he can take with minimum capacity 0 and maximum capacity 1.
• Each class node is linked to the sink t with minimum capacity equal to the minimum number of students that need to take the class and maximum capacity equal to the maximum number of students that can take the class.

Now, for the algorithm, you can use Ford Fulkerson on an appropriately transformed graph where all minimum flow constraints are set to 0.

A possible transformation is given here. Lemma 1. proves that if you find a max flow saturating all arcs exiting the new source(and entering the new sink) in the transformed graph then a feasible solution on original graph exists thus a valid scheduling exists.