Student-Project Allocation with Preferences over Projects
Student-Project Allocation with Preferences over Projects
复制标题
学生项目分配优先于项目
DOI：
10.1016/j.jda.2008.07.003
复制
发表时间：
2008
影响因子：
--
通讯作者：
Gregg O'Malley
中科院分区：
文献类型：
--
作者：
D. Manlove;Gregg O'Malley
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, unless P=NP. On the other hand, we give an approximation algorithm with a performance guarantee of 2 for max-spa-p.
