No se me ocurre ningún problema "bien entendido" al que reducirlo fácilmente, pero sí he pensado en la solución. En primer lugar, creo que la restricción de trabajo mínimo ( $\sum_i Tij \leq \sum_i Tij′$ (para $j \neq j'$ ) sólo se permite si no hay forma de que uno de los alumnos vigilados por $T_j′$ podría darse a $T_j$ ) es demasiado fuerte para conseguirlo. Consideremos el caso de 3 profesores, de los cuales sólo uno tiene alumnos que aprueban el examen escrito, y tiene un número impar de alumnos que aprueban. Entonces, los alumnos que aprueben deberán repartirse lo más equitativamente posible entre los otros dos profesores, con lo que uno tendrá más alumnos que el otro. Así, el profesor con más querría enviar un alumno al profesor con menos alumnos, tras lo cual se invertirían sus papeles. La "restricción de trabajo mínimo" nunca se lograría. En su lugar, propongo que se exija que $\sum_i Tij - \sum_i Tij' > 1$ sólo si $j$ no puede enviar a un estudiante a $j'$ .
Creo que el problema de optimización puede resolverse en dos fases. Creo que un simple algoritmo codicioso para la primera fase debería funcionar bien. Sin pérdida de generalidad, supongamos que $T_1$ ha aprobado el mayor número de estudiantes, $T_2$ el segundo más, y así sucesivamente (rompiendo los empates arbitrariamente).
La primera fase se produce en $t$ rondas. En la primera ronda, $T_1$ asigna a sus alumnos que pasan a $T_2$ a través de $T_t$ de la manera más uniforme posible, de modo que la diferencia entre el número máximo de estudiantes y el número mínimo de estudiantes asignados a $T_2$ a través de $T_t$ es como máximo $1$ . En las rondas siguientes, los profesores restantes asignan sus alumnos de paso a los otros profesores, asignando siempre primero a los alumnos a la profesora que tiene menos alumnos asignados. Por ejemplo (suponiendo que $T_1$ tenía al menos $t-1$ los estudiantes aprueban), $T_2$ asignará a sus alumnos de paso a $T_1$ hasta $T_1$ tiene uno menos que el número máximo de alumnos asignados a cualquier profesor.
Durante cualquier ronda de la primera fase, deja que $M$ denotan el número máximo de alumnos asignados a cualquier profesor. Llamar a un profesor $T_i$ "deficiente" si ha asignado menos de $M-1$ estudiantes. Debería ser fácil convencerse de que puede haber como máximo $1$ profesor deficiente después de cualquier ronda de la primera fase. Por ejemplo, después de la primera ronda, $T_1$ es el único profesor que podría ser deficiente. Después de la segunda ronda, $T_1$ o $T_2$ (pero no ambos) podrían ser deficientes, etc.
Al final de la fase 1, si ningún profesor es deficiente, todos los profesores tienen al menos $M-1$ estudiantes asignados, y todo es tan justo como podría ser. De lo contrario, sólo hay que rectificar la deficiencia de un solo profesor, por lo que tenemos que tener una fase 2.
Creo que la fase 2 también puede llevarse a cabo con avidez. Supongamos que $T_i$ es deficiente. A continuación, elija un jugador $T_j$ con $M$ estudiantes, y hacer que done un estudiante a $T_i$ . Si esto es imposible, debe ser porque todos los jugadores con estudiantes M sólo tienen estudiantes de $T_i$ 's homeroom. Así que mira a los profesores con $M-1$ estudiantes y (si es posible) que uno de ellos, digamos $T_k$ donar un estudiante a $T_i$ . Entonces, tenga $T_j$ donar un estudiante a $T_k$ (esto es posible porque todos los $T_j$ Los estudiantes de la Universidad de Barcelona provienen de $T_i$ ). Después de este intercambio, $T_i$ sigue siendo la única posibilidad de deficiencia. Continúe hasta que $T_i$ ya no es deficiente, o hasta que ningún jugador pueda donar un alumno a $T_i$ . En este punto, deberíamos tener una configuración óptima.
Creo que el tiempo de ejecución de este algoritmo debería ser óptimo hasta un factor de 2 porque cada estudiante cambia de mano como máximo dos veces. No he revisado los detalles con demasiado cuidado, pero creo que este algoritmo (o una ligera variación del mismo) debería hacer el trabajo.
