<XML><RECORDS><RECORD><REFERENCE_TYPE>0</REFERENCE_TYPE><REFNUM>8078</REFNUM><AUTHORS><AUTHOR>Abraham,D.J.</AUTHOR><AUTHOR>Irving,R.W.</AUTHOR><AUTHOR>Manlove,D.F.</AUTHOR></AUTHORS><YEAR>2007</YEAR><TITLE>Two Algorithms for the Student-Project Allocation Problem</TITLE><PLACE_PUBLISHED>Journal of Discrete Algorithms vol. 5</PLACE_PUBLISHED><PUBLISHER>Elsevier Science</PUBLISHER><PAGES>73-90</PAGES><ISBN>1570-8667</ISBN><LABEL>Abraham:2007:8078</LABEL><KEYWORDS><KEYWORD>Stable matching problem; Preference lists; Linear-time algorithm; Student-optimal; Lecturer-optimal</KEYWORD></KEYWORDS<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.</ABSTRACT><URL>http://dx.doi.org/10.1016/j.jda.2006.03.006</URL></RECORD></RECORDS></XML>