Computing at Glasgow University
Paper ID: 7952

Student-project allocation with preferences over projects
Manlove,D.F. O'Malley,G.

Publication Type: Conference Proceedings
Appeared in: 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
Publisher: N/A
Year: 2005
ISBN/ISSN: 1-904987-10-9

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

PDF Bibtex entry Endnote XML