<XML><RECORDS><RECORD><REFERENCE_TYPE>0</REFERENCE_TYPE><REFNUM>8552</REFNUM><AUTHORS><AUTHOR>Manlove,D.F.</AUTHOR><AUTHOR>O'Malley,G.</AUTHOR></AUTHORS><YEAR>2008</YEAR><TITLE>Student-project allocation with preferences over projects</TITLE><PLACE_PUBLISHED>Journal of Discrete Algorithms, volume 6</PLACE_PUBLISHED><PUBLISHER>Elsevier Science</PUBLISHER><PAGES>553-560</PAGES><LABEL>Manlove:2008:8552</LABEL><KEYWORDS><KEYWORD>Matching problem; Stable matching; NP-hardness; Approximation hardness; Approximation algorithm</KEYWORD></KEYWORDS<ABSTRACT>We study the problem of allocating students to projects, where both students and lecturers have preferences over projects, and both projects and lecturers have capacities. In this context we seek a <i>stable matching</i> of students to projects, which respects these preference and capacity constraints. Here, the stability definition generalises the corresponding notion in the context of the classical Hospitals / Residents problem. We show that stable matchings can have different sizes, which motivates MAX-SPA- P, the problem of finding a maximum cardinality stable matching. We prove that MAX-SPA-P is NP-hard and not approximable within d, for some d, unless P=NP. On the other hand, we give an approximation algorithm with a performance guarantee of 2 for MAX-SPA-P.</ABSTRACT><URL>http://dx.doi.org/10.1016/j.jda.2008.07.003</URL></RECORD></RECORDS></XML>