Paper Info
Title
The Student-Project Allocation Problem
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 linear-time 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.
Year
DOI
Venue
2003
10.1007/978-3-540-24587-2_49
ALGORITHMS AND COMPUTATION, PROCEEDINGS
Keywords
Field
DocType
stable matching
Speech processing,Generalization,Computer science,Image processing,Artificial intelligence,Time complexity,Minimum time
Conference
Volume
ISSN
Citations 
2906
0302-9743
11
PageRank 
References 
Authors
0.94
14
3
Name
Order
Citations
PageRank
David J. Abraham119015.88
Robert W. Irving21331146.76
David F. Manlove376160.45