UNIVERSITY of GLASGOW

Computing at Glasgow University
 
Paper ID: 7099

The Student-Project Allocation Problem
Abraham,D.J. Irving,R.W. Manlove,D.F.

Publication Type: Conference Proceedings
Appeared in: Proceedings of ISAAC 2003: The 14th Annual International Symposium on Algorithms and Computation, volume 2906 of Lecture Notes in Computer Science
Page Numbers : 474-484
Publisher: Springer Verlag
Year: 2003
ISBN/ISSN: 3-540-20695-7

URL: This publication is available at this URL.

Abstract:

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 an optimal lineartime algorithm for allocating students to projects, subject to these preferences and capacities. In particular, the 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 our algorithm is simultaneously best-possible for all students. The SPA problem model that we consider is very general and has applications to a range of different contexts besides student-project allocation.


PDF Bibtex entry Endnote XML