Computing at Glasgow University
Paper ID: 8078

Two Algorithms for the Student-Project Allocation Problem
Abraham,D.J. Irving,R.W. Manlove,D.F.

Publication Type: Journal
Appeared in: Journal of Discrete Algorithms vol. 5
Page Numbers : 73-90
Publisher: Elsevier Science
Year: 2007
ISBN/ISSN: 1570-8667

URL: This publication is available at this URL.


We study the Student-Project Allocation problem (SPA), a generalisation of the classical Hospitals / Residents problem (HR). An instance of SPA involves a set of students, projects and lecturers. Each project is offered by a unique lecturer, and both projects and lecturers have capacity constraints. Students have preferences over projects, whilst lecturers have preferences over students. We present two optimal linear-time algorithms for allocating students to projects, subject to the preference and capacity constraints. In particular, each algorithm finds a stable matching of students to projects. Here, the concept of stability generalises the stability definition in the HR context. The stable matching produced by the first algorithm is simultaneously best-possible for all students, whilst the one produced by the second algorithm is simultaneously best-possible for all lecturers. We also prove some structural results concerning the set of stable matchings in a given instance of SPA. The SPA problem model that we consider is very general and has applications to a range of different contexts besides student-project allocation.

Keywords: Stable matching problem; Preference lists; Linear-time algorithm; Student-optimal; Lecturer-optimal

PDF Bibtex entry Endnote XML