Practical Collaboration

This web page describes some practical matching schemes that incorporate algorithms developed by members of the Algorithms group at the School of Computing Science, University of Glasgow.

Scottish Foundation Allocation Scheme (NHS Education for Scotland)
The Scottish Foundation Allocation Scheme is the centralised matching scheme that allocates medical graduates to two-year Foundation programmes in Scottish hospitals. The scheme takes as input the preferences of students over programmes (currently each student's preference list must be of length 6), those of Foundation tutors over students (these preference lists may include ties), and the number of posts that each programme has. Our algorithm then constructs a stable matching of students to programmes based on these preference lists and capacity constraints; the algorithm also tries to match as many students as possible.
Reference: R.W. Irving, Matching medical students to pairs of hospitals: a new variation on a well-known theme, in Proceedings of ESA'98, the Sixth Annual European Symposium on Algorithms, Venice Italy, 1998, Lecture Notes in Computer Science, vol. 1461, pp. 381-392, Springer, 1998.

National Matching Scheme for Paired Donation (NHS Blood and Transplant)
NHS Blood and Transplant run the National Matching Scheme for Paired (kidney) Donation in the UK. This utilises their database of incompatible (donor,patient) pairs who would be willing to participate in a live-donor kidney exchange with one or more other (donor,patient) pairs. Every three months a matching run is carried out, and our algorithms are used to find an optimal set of exchanges. At present paired (involving two couples) and pooled (involving three couples) exchanges are sought.
Reference: P. Biró, D.F. Manlove and R. Rizzi, Maximum weight cycle packing in directed graphs, with application to kidney exchange programs, Discrete Mathematics, Algorithms and Applications, 1 (4) : 499-517, 2009. Postprint. Some publicity about the collaboration: 1, 2, 3, 4, 5, 6, 7, 8, 9.

Student-Project Allocation (University of Glasgow, School of Computing Science, and University of Kent, School of Biosciences)
Level 4 undergraduate students undertake an individual project as part of their curriculum. Members of staff publicise project proposals, which students then browse. They are asked to rank 5 projects in order of preference. Our matching algorithms then construct an allocation of students to projects that optimises the cardinality of the matching (in other words, the number of students assigned to projects), and then subject to this objective, the algorithms optimise the profile of the matching in a precise sense (the profile of a matching is the number of students assigned to their first, second, third choice etc.) The algorithms can also take into account upper bounds from staff indicating the maximum number of students that they are willing to supervise.
In October 2011, these algorithms were also used to allocate students to projects in the School of Biosciences at the University of Kent.
Reference: D.J. Abraham, R.W. Irving and D.F. Manlove, Two algorithms for the Student-Project Allocation problem, Journal of Discrete Algorithms, 5 (1) :73-90, 2007. Postprint.

Virtual Administration and Learning Environment (University of Glasgow, School of Medicine)
Senior undergraduate students in the School of Medicine at the University of Glasgow are required to choose a range of optional courses, each of which has an upper limit on the number of students that can take that course. Students form preference lists over the elective courses that they are interested in, which they upload via the VALE portal. These lists, together with the course capacities, are then passed as input to our optimal matching algorithms which construct allocations of students to courses. As in the case of student-project allocation above, the primary objective is to maximise the cardinality of the matching (i.e., the number of students who are allocated to an acceptable course). Subject to this condition, the profile of the matching is then optimised. These algorithms are also utilised in the Medical Faculty in other contexts, for example in the assignment of medical students to short-term hospital placements, again based on their preference lists over the available posts.
Reference: R.W. Irving, T. Kavitha, K. Mehlhorn, D. Michail and K. Paluch, Rank-maximal matchings, ACM Transactions on Algorithms, 2 : 602-610, 2006.

More information about these and other practical matching schemes can be found here.