Student-Project Allocation with preferences over Projects ?
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 maximum cardinality stable matching. We prove that max-spa-p is NP-hard and not approximable within ? , for some ?>1 ? > 1 , unless P=NP P = NP . On the other hand, we give an approximation algorithm with a performance guarantee of 2 for max-spa-p.
stable matching np-hardness approximation algorithm matching problem approximation hardness