Name
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 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. |
Year | DOI | Venue |
|---|---|---|
2007 | 10.1016/j.jda.2006.03.006 | J. Discrete Algorithms |
Keywords | Field | DocType |
student-project allocation problem,stable matching problem,student-optimal,preference lists,optimal linear-time algorithm,linear-time algorithm,lecturer-optimal,stable matching,spa problem model,residents problem,capacity constraint,hr context,whilst lecturer,stability definition,stable matchings | Stable roommates problem,Combinatorics,Stable marriage problem,Generalization,Computer science,Algorithm | Journal |
Volume | Issue | ISSN |
5 | 1 | Journal of Discrete Algorithms |
Citations | PageRank | References |
26 | 1.49 | 14 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| David J. Abraham | 1 | 190 | 15.88 |
| Robert W. Irving | 2 | 1331 | 146.76 |
| David F. Manlove | 3 | 761 | 60.45 |