Summer School of DeCAn. Day 2

Speaker: Katarína Cechlárová (Professor, P. J. Šafárik University Košice, Faculty of Science, Slovakia)
Title: The Teachers Assignment Problem

Abstract
In this talk we describe a new real application of the matching theory that concerns the placement of pre-service teachers to practical placement to schools. First we briefly review the history and organization of the teachers study in the Slovak and Czech educational system and the aims and current practices of practical placements. Then we formally define the Teachers Assignement Problem (briefly TAP) and present in detail its combinatorial structure. The aim of the university staff is to find a place for each student. However, as each student specializes in two different subjects, she needs two supervisiors at the placement school and since the schools may have different capacities for different subjects, the problem to maximize the number of placed students is NP-hard. This intractability result holds even under several strong restrictions concerning the total number of subjects, partial capacities of schools and the number of acceptable schools each teacher is allowed to list. Therefore we present an integer programming model and its application to real data. We also propose several approximation algorithms and show their approximation guarantee. In the second part of the talk we allow for preferences of students and schools. In this case, a stable solution is sought and we present an appropriate stability definition. Again, we show that the problem to decide whether a stable solution exists is NP-complete, unless the preferences of the students or of the schools are derived from a common master list. Finally, we prove a strong inapproximability result for minimization of the number of blocking pairs.