DLS: Algorithms for healthcare-related matching problems

Event details

  • When: 31st March 2017 09:15 - 15:30
  • Where: Lower College Hall
  • Series: Distinguished Lectures Series
  • Format: Distinguished lecture

Algorithms for healthcare-related matching problems

Distinguished Lecture Series, Semester 2, 2016-7

David Manlove

School of Computing Science, University of Glasgow

9.25am – 3.30pm, Friday 31 March

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


Algorithms arise in numerous everyday appPicture of David Manlovelications – 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).


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.


Distinguished Lecture Series 2016: Prof. Julie McCann

Earlier this month Professor Julie McCann from Imperial College London, delivered the next set of distinguished lectures for 2016, in Lower and Upper College Hall. The three topical, well attended and interesting lectures centred around Distributed Systems and Sensing and discussed how sensor networks are being used today, how other sciences will impact the research area, how such systems are programmed and finished by introducing ongoing challenges in terms of scalability, resilience and security.

Professor McCann is pictured below at various stages of the distinguished lecture series, and with Director of Research, Professor Simon Dobson and Dean of Science, Professor Alan Dearle.



Videos from the DLS can be accessed on Vimeo –
Lecture 1: https://vimeo.com/192134381
Lecture 2: https://vimeo.com/192135351
Lecture 3: https://vimeo.com/192137007

Images courtesy of Saleem Bhatti

School of Computer Science: Distinguished Lecture Series

The School of Computer Science in the University of St Andrews is pleased to announce the next set of Distinguished Lectures (DLS) leading up to the 50th anniversary of the series in 2019.

The next DLS will be delivered by Maria Klawe the president of Harvey Mudd College and former president of the ACM (Association of Computing Machinery) on Thursday March 31st, location to be confirmed.

The well attended Distinguished Lecture Series were initiated by Professor Jack Cole in 1969 with a view to exposing students and other interested parties to leading edge topics in Computer Science.

Professor Jack Cole

Professor Jack Cole

All alumni of the school are invited to return and join us in St Andrews for the DLS, and In time we will extend further invitations to the larger 50th Anniversary events in 2019.

Previous Distinguished Lectures held in Lower College Hall and The Byre Theatre

Previous Distinguished Lectures held in Lower College Hall and The Byre Theatre

Distinguished Lecture Series 2015: Joe Armstrong

Earlier this week Professor Joe Armstrong from the KTH Royal Institute of Technology in Stockholm, delivered the second set of distinguished lectures for 2015, in the Byre Theatre. The three topical, well attended and interesting lectures centred around the question “Scalability and fault-tolerance, are they the same?”



Images courtesy of Saleem Bhatti

Distinguished Lecture Series 2014: Luca Cardelli

The 2014 Distinguished Lecture Series took place on Tuesday in Lower College Hall. This year’s speaker Prof Luca Cardelli of Microsoft Research and the University of Oxford, delivered three lectures involving Morphisms of Reaction Networks that Couple Structure to Function.

Slides from the lectures are now available: http://lucacardelli.name/indexTalks.html

Luca pictured in Lower College Hall on Tuesday

Luca pictured in Lower College Hall on Tuesday

The mechanisms underlying complex biological systems are routinely represented as networks. Network kinetics is widely studied, and so is the connection between network structure and behavior. But it is the relationships between network structures that can reveal similarity of mechanism.

We define morphisms (mappings) between reaction networks that establish structural connections between them. Some morphisms imply kinetic similarity, and yet their properties can be checked statically on the structure of the networks. In particular we can determine statically that a complex network will emulate a simpler network: it will reproduce its kinetics for all corresponding choices of reaction rates and initial conditions. We use this property to relate the kinetics of many common biological networks of different sizes, also relating them to a fundamental population algorithm. Thus, structural similarity between reaction networks can be revealed by network morphisms, elucidating mechanistic and functional aspects of complex networks in terms of simpler networks.

Tuesday’s Programme:
09:15-09:30 Introduction by Prof Simon Dobson

09:39-10:30 Lecture 1 – Molecular Programming

11:00-12:00 Lecture 2 – The Cell Cycle Switch Computes Approximate Majority

13:30-14:30 Lecture 3 – Morphisms of Chemical Reaction Networks

14:30-15:30 Q & A Session

Image courtesy of Prof Saleem Bhatti