The Student-Project Allocation Problem: structure and algorithms

In this thesis we study the Student-Project Allocation problem (SPA), which is a matching problem based on the allocation of students to projects and lecturers. Students have preferences over projects, where each project is offered by one lecturer; whilst lecturers have preferences over students, or over the projects that they offer. We seek stable matchings of students to projects, which guarantee that no student and lecturer have an incentive to deviate from the matching by forming a private arrangement involving some project. We present new structural and algorithmic results for four problems related to SPA . We begin by characterising the stable matchings in an instance of the Student-Project Allocation problem with Lecturer preferences over Students (SPA-S) where the preferences are strictly ordered, in the special case that for each student in the instance, all of the projects in her preference list are offered by different lecturers. We achieve this characterisation by showing that, under this restriction, the set of stable matchings in an instance of SPA-S is a distributive lattice with respect to a natural dominance relation. Next, we study a variant of SPA - S where the preferences may involve ties — the Student- Project Allocation problem with Lecturer preferences over Students with Ties (SPA-ST). The presence of ties in the preference lists gives rise to three different concepts of stability, namely, weak stability, strong stability, and super-stability. We investigate stable matchings under the super-stability (respectively strong stability) concept. We present the first polynomial-time algorithm to find a super-stable (respectively strongly stable) matching or to report that no such matching exists, given an instance of SPA-ST . We also prove some structural results concerning the set of super-stable (respectively strongly stable) matchings in a given instance of SPA - ST . Further, we present results obtained from an empirical evaluation of our algorithms based on randomly-generated SPA-ST instances. Moving away from variants of SPA with lecturer preferences over students, we study the Student-Project Allocation problem with lecturer preferences over Projects (SPA-P). In this context it is known that stable matchings can have different sizes and the problem of finding a maximum size stable matching, denoted MAX-SPA-P , is NP-hard. There are two known approximation algorithms for MAX-SPA-P , with performance guarantees 2 and 3/2 . We show that MAX-SPA-P is polynomial-time solvable if there is only one lecturer involved, and NP-hard to approximate within some constant c > 1 if there are two lecturers involved. We also show that this problem remains NP-hard if each preference list is of length at most 3, with an arbitrary number of lecturers. We then describe an Integer Programming (IP) model to enable MAX-SPA-P to be solved optimally in the general case. Following this, we present results arising from an empirical evaluation that investigates how the solutions produced by the approximation algorithms compare to optimal solutions obtained from the IP model, with respect to the size of the stable matchings constructed, on instances that are both randomly-generated and derived from real datasets