We study the problem of allocating students to projects, where both students and lecturers have preferences over projects, and both projects and lecturers have capacities. In this context we seek a stable matching of students to projects, which respects these preference and capacity constraints. Here, the stability definition generalises the corresponding notion in the context of the classical Hospitals / Residents problem. We show that stable matchings can have different sizes, which motivates max-spa-p, the problem of finding a maximum cardinality stable matching. We prove that max-spa-p is NP-hard and not approximable within δ, for some δ > 1, unless P=NP. On the other hand, we give an approximation algorithm with a performance guarantee of 2 for max-spa-p.
Ref. REF studied the SPA problem in which students and lecturers have preferences over projects.
Student project allocation with preferences over projects
In Proceedings of ACID 2005: the 1st Algorithms and Complexity in Durham workshop, volume 4 of Texts in Algorithmics
Mathematics Computer Science