<XML><RECORDS><RECORD><REFERENCE_TYPE>3</REFERENCE_TYPE><REFNUM>7952</REFNUM><AUTHORS><AUTHOR>Manlove,D.F.</AUTHOR><AUTHOR>O'Malley,G.</AUTHOR></AUTHORS><YEAR>2005</YEAR><TITLE>Student-project allocation with preferences over projects</TITLE><PLACE_PUBLISHED>In Proceedings of ACID 2005: the 1st Algorithms and Complexity in Durham workshop, volume 4 of Texts in Algorithmics, KCL Publications</PLACE_PUBLISHED><PUBLISHER>N/A</PUBLISHER><PAGES>69-80</PAGES><ISBN>1-904987-10-9</ISBN><LABEL>Manlove:2005:7952</LABEL><KEYWORDS><KEYWORD>Matching problem; Stable matching; NP-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 stable matching 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, and the problem of finding a maximum cardinality stable matching is NP-hard, though approximable within a factor of 2.</ABSTRACT></RECORD></RECORDS></XML>