کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
430909 | 688229 | 2008 | 8 صفحه PDF | دانلود رایگان |
![عکس صفحه اول مقاله: Student-Project Allocation with preferences over Projects Student-Project Allocation with preferences over Projects](/preview/png/430909.png)
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=NPP=NP. On the other hand, we give an approximation algorithm with a performance guarantee of 2 for max-spa-p.
Journal: Journal of Discrete Algorithms - Volume 6, Issue 4, December 2008, Pages 553–560