The "Waiting lists problem"

Question

A number of students want to get into sections for a class, some are already signed up for one section but want to change section, so they all get on the wait lists. A student can get into a new section only if someone drops from that section. No students are willing to drop a section they are already in unless that can be sure to get into a section they are waiting for. The wait list for each section is first come first serve.

Get as many students into their desired sections as you can.

The stated problem can quickly devolve to a gridlock scenario. My question is; are there known solutions to this problem?

---

One trivial solution would be to take each section in turn and force the first student from the waiting list into the section and then check if someone end up dropping out when things are resolved (O(n) or more on the number of section). This would work for some cases but I think that there might be better options involving forcing more than one student into a section (O(n) or more on the student count) and/or operating on more than one section at a time (O(bad) :-)

Answer 1

Well, this just comes down to finding cycles in the directed graph of classes right? each link is a student that wants to go from one node to another, and any time you find a cycle, you delete it, because those students can resolve their needs with each other. You're finished when you're out of cycles.

Answer 2

This is actually a Graph problem. You can think of each of these waiting list dependencies as edges on a directed graph. If this graph has a cycle, then you have one of the situations you described. Once you have identified a cycle, you can chose any point to "break" the cycle by "over filling" one of the classes, and you will know that things will settle correctly because there was a cycle in the graph.

Answer 3

Ok, lets try. We have 8 students (1..8) and 4 sections. Each student is in a section and each section has room for 2 students. Most students want to switch but not all.

In the table below, we see the students their current section, their required section and the position on the queue (if any).

+------+-----+-----+-----+
| stud | now | req | que |
+------+-----+-----+-----+
|    1 |   A |   D |   2 |
|    2 |   A |   D |   1 |
|    3 |   B |   B |   - |
|    4 |   B |   A |   2 |
|    5 |   C |   A |   1 |
|    6 |   C |   C |   - |
|    7 |   D |   C |   1 |
|    8 |   D |   B |   1 |
+------+-----+-----+-----+

We can present this information in a graph:

+-----+           +-----+           +-----+
|  C  |---[5]--->1|  A  |2<---[4]---|  B  |
+-----+           +-----+           +-----+
   1               |   |               1
   ^               |   |               ^
   |              [1] [2]              |
   |               |   |               |
  [7]              |   |              [8]
   |               V   V               |
   |               2   1               |
   |              +-----+              |
   \--------------|  D  |--------------/
                  +-----+

We try to find a section with a vacancy, but we find none. So because all sections are full, we need a dirty trick. So lets take a random section with a non empty queue. In this case section A and assume, it has an extra position. This means student 5 can enter section A, leaving a vacancy at section C which is taken by student 7. This leaves a vacancy in section D which is taken by student 2. We now have a vacancy at section A. But we assumed that section A has an extra position, so we can remove this assumption and have gained a simpler graph.

If the path never returned to section A, undo the moves and mark A as an invalid startingpoint. Retry with another section. If there are no valid sections left we are finished.

Right now we have the following situation:

+-----+           +-----+           +-----+
|  C  |           |  A  |1<---[4]---|  B  |
+-----+           +-----+           +-----+
                   |                   1
                   |                   ^
                  [1]                  |
                   |                   |
                   |                  [8]
                   V                   |
                   1                   |
                  +-----+              |
                  |  D  |--------------/
                  +-----+

We repeat the trick with another random section, and this solves the graph.

If you start with several students currently not assigned, you add an extra dummy section as their startingpoint. Of course, this means that there must be vacancies in any sections or the problem is not solvable.

Note that due to the order in the queue, it can be possible that there is no solution.