Paper ID: 8552
Student-project allocation with preferences over projects
Journal of Discrete Algorithms, volume 6
Page Numbers : 553-560
Publisher: Elsevier Science
URL: This publication is available at this URL.
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, 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.
Keywords: Matching problem; Stable matching; NP-hardness; Approximation hardness; Approximation algorithm