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 was the centralised matching scheme that, until recently, allocated medical graduates to two-year Foundation programmes in Scottish hospitals. The scheme took as input the preferences of applicants over programmes, the “scores” of the applicants (based on academic merit and performance in Situational Judgement Tests) which gave rise to a “master list” of applicants (possibly involving ties, and from which the programmes’ preferences were derived), and the number of posts that each programme had. Between 1999-2012, our algorithms were used to construct stable matchings of applicants to programmes based on these preference lists and capacity constraints; the algorithm also tried to match as many applicants 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 Living Donor Kidney Sharing Schemes (NHS Blood and Transplant)

 

The National Living Donor Kidney Sharing Schemes (NLDKSS) is a matching scheme run by NHS Blood and Transplant and used to find optimal sets of kidney exchanges in the UK.  It is run every quarter and has been in existence since April 2007.  It currently finds optimal solutions involving pairwise and 3-way exchanges and additionally allows altruistic donors to be involved in domino paired donation (DPD) chains involving one couple.  Software developed by us has been used to find an optimal solution at each quarterly run since July 2008.  As of April 2013, 196 actual transplants identified by the software have taken place.

 

Reference: D.F. Manlove and G O’Malley, Paired and altruistic kidney donation in the UK: Algorithms and experimentation, in Proceedings of SEA 2012: the 11th International Symposium on Experimental Algorithms, volume 7276 of Lecture Notes in Computer Science, pages 271-282, Springer, 2012.  Postprint

 

Some publicity about the collaboration: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10.

 

 

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.

Description: Description: Description: Description: Description: media_32250_en

 

In recent years these algorithms were also used to allocate students to projects in the School of Biosciences at the University of Kent.

 

Description: Description: Description: Description: C:\Users\davidm\Desktop\kent.jpg

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.

Description: Description: Description: Description: Description: dj_logo

 

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.