I have a sort of matching problem. I am wondering if you know if this problem reduces to a familiar one.
It arises from my friend's job, and something we were wondering about this morning on the train. She teaches a language, and she and her colleagues are currently giving a TOEFL-like exam. It has two parts over two days. The first day students take a computerized test. Those who pass the computerized test take an oral exam the second day. Each student must have two teachers listening to their oral, but the teacher may not be the teacher who taught their homeroom. The problem is how to match teachers to students, respecting the no-homeroom constraint such that the work load on the teachers is minimal.
A note: some teachers will probably have more students pass the first part of the exam than others.
More precisely:
- There are students $S_i$ for $i=1,\dots,s$.
- There are teachers $T_j$for $j=1,\dots,t$.
- There are classes $C_k$ for $k=1,\dots,c$, where the number of the class corresponds to the index of its homeroom teacher.
We would like that $min(\sum_i^s T_{ij})$ is attained (where $T_{ij}$ takes value 1 if teacher $j$ sits watches the exam of student $i$ and 0 if they do not) subject to the constraints that:
- No homeroom constraint: $i \ne j$.
- Minimal work constraint $\sum_i^s T_{ij} \le \sum_i^s T_{ij'}$ (for $j \ne j'$) is allowed only if there is no way that one of the students watched by $T_{j'}$ could be given to $T_j$.
Question: Do you know if this reduces to a familiar problem (I don't know, bin packing or something unexpected like that)?
I can't think of any "well understood" problem to easily reduce it to, but I did give some thought to the solution. First, I think the minimal work constraint ($\sum_i Tij \leq \sum_i Tij′$ (for $j \neq j'$) is allowed only if there is no way that one of the students watched by $T_j′$ could be given to $T_j$) is too strong to achieve. Consider the case with 3 teachers, only one of whom has any students pass the written exam, and she has an odd number of students pass. Then the students who pass should be distributed as evenly as possible among the other two teachers, resulting in one having more students than the other. Thus, the teacher with more would want to send a student to the teacher with fewer students, after which their roles would be reversed. The "minimal work constraint" would never be achieved. Instead I propose that we should require that $\sum_i Tij - \sum_i Tij' > 1$ only if $j$ can't send a student to $j'$.
I think the optimization problem can be solved in two phases. I think a simple greedy algorithm for the first phase should work well. Without loss of generality, assume that $T_1$ passed the most students, $T_2$ the second most, and so on (breaking ties arbitrarily).
The first phase occurs in $t$ rounds. In the first round, $T_1$ assigns her passing students to $T_2$ through $T_t$ as evenly as possible, so that the difference between the maximum number of students and the minimum number of students assigned to $T_2$ through $T_t$ is at most $1$. In subsequent rounds, the remaining teachers assign their passing students to the other teachers, always assigning students first to the teacher with the fewest students assigned to her. For example (assuming $T_1$ had at least $t-1$ students pass), $T_2$ will assign her passing students to $T_1$ until $T_1$ has one less than the maximum number of students assigned to any teacher.
During any round of the first phase, let $M$ denote the maximum number of students assigned to any teacher. Call a teacher $T_i$ "deficient" if she has assigned fewer than $M-1$ students. It should be easy to convince yourself that there can be at most $1$ deficient teacher after any round of the first phase. For example, after the first round, $T_1$ is the only teacher who could possibly be deficient. After the second round, $T_1$ or $T_2$ (but not both) could be deficient, etc.
At the end of phase 1, if no teacher is deficient, then all teachers have at least $M-1$ students assigned to them, and everything is as fair as it could be. Otherwise, we need only rectify the deficiency of a single teacher, so we have to have a phase 2.
I think phase 2 can be carried out greedily as well. Suppose $T_i$ is deficient. Then choose a player $T_j$ with $M$ students, and have her donate a student to $T_i$. If this is impossible, it must be because all players with M students only have students from $T_i$'s homeroom. So look at teachers with $M-1$ students and (if possible) have one of them, say $T_k$, donate a student to $T_i$. Then have $T_j$ donate a student to $T_k$ (this is possible because all of $T_j$'s students come from $T_i$). After this exchange, $T_i$ is still the only possibility for deficiency. Continue until either $T_i$ is no longer deficient, or until no player can donate a student to $T_i$. At this point, we should have an optimal configuration.
I think the run-time of this algorithm should be optimal up to a factor of 2 because each student changes hands at most twice. I haven't gone over the details too carefully, but I think that this algorithm (or a slight variation thereof) should definitely get the job done.