UNIVERSITY of GLASGOW

Computing at Glasgow University
 
Paper ID: 8552

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

Publication Type: Journal
Appeared in: Journal of Discrete Algorithms, volume 6
Page Numbers : 553-560
Publisher: Elsevier Science
Year: 2008
ISBN/ISSN:

URL: This publication is available at this URL.

Abstract:

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 a maximum cardinality stable matching. We prove that MAX-SPA-P is NP-hard and not approximable within d, for some d, unless P=NP. On the other hand, we give an approximation algorithm with a performance guarantee of 2 for MAX-SPA-P.

Keywords: Matching problem; Stable matching; NP-hardness; Approximation hardness; Approximation algorithm


PDF Bibtex entry Endnote XML