Paper ID: 7952
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, KCL Publications
Page Numbers : 69-80
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, and the problem of finding a maximum cardinality stable matching is NP-hard, though approximable within a factor of 2.
Keywords: Matching problem; Stable matching; NP-hardness; Approximation algorithm