Algorithms for healthcare-related matching problems

Distinguished Lecture Series, Semester 2, 2016-7

David Manlove

School of Computing Science, University of Glasgow

Lower College Hall (with overflow simulcast in Upper College Hall)

Abstract:

Algorithms arise in numerous everyday applications – in this series of lectures I will describe how algorithms can be used to solve matching problems having applications in healthcare settings.  I will begin by outlining how algorithms can be designed to cope with computationally hard problems.  I will then describe algorithms developed at the University of Glasgow that have been used by the NHS to solve two particular matching problems.  These problems correspond to the annual assignment of junior doctors to Scottish hospitals, and finding “kidney exchanges” between kidney patients and their incompatible donors in the UK.

Biography: Dr David Manlove is a Senior Lecturer in Computing Science at the University of Glasgow, where he has been since 1995. He is interested in algorithms for problems involving matching agents to commodities (e.g., junior doctors to hospitals, kidney patients to donors) in the presence of ordinal preferences or cardinal utilities. He has written or co-authored over 60 papers in this area, and his book “Algorithmics of Matching Under Preferences” was published in 2013. Much of this research has involved designing algorithms to cope with NP-hard optimisation problems arising in healthcare-related settings, working in collaboration with the National Health Service in the UK. He is Vice-Chair of the ENCKEP COST Action (European Network for Collaboration on Kidney Exchange Programmes).

Timetable:

9.25 Introduction

9.30 Lecture 1: Designing Algorithms for Computationally Hard Problems

10.30 Break

10.45 Refreshments (Upper College Hall)

11.15 Lecture 2: Algorithms for Junior Doctor Allocation

12.15 Lunch (not provided)

2.15 Lecture 3: Algorithms for Kidney Exchange

3.15 Discussion

3.30 Close

Lecture 1: Designing Algorithms for Computationally Hard Problems

I will begin by explaining why it is important to design efficient algorithms, and where computational hardness presents a barrier.  Through the example of the Travelling Salesman Problem I will describe algorithmic techniques for coping with hard problems, including branch and bound, integer programming and approximation algorithms.  You will see a route for an optimal pub-crawl around St Andrews!

Lecture 2: Algorithms for Junior Doctor Allocation

Between 1999-2012, NHS Education for Scotland ran a matching scheme for allocating junior doctors to 2-year foundation posts at Scottish hospitals.  I will describe the application, the underlying (computationally hard) problems, the algorithms that we developed for this application and some empirical results arising from real data connected with the matching scheme in recent years.

Lecture 3: Algorithms for Kidney Exchange

Since 2007, NHS Blood and Transplant have run the National Living Donor Kidney Sharing Schemes.  Every quarter a matching run is carried out in which an optimal set of “kidney exchanges” is sought.  Again I will outline the application, the underlying computational problems and indicate how integer programming can be used to find optimal solutions.  I will then give an overview of the transplants identified by the algorithm for recent matching runs.