Algorithms and Complexity
Algorithms and Complexity research at Glasgow focuses on the theoretical design and analysis of efficient algorithms, establishing whether problems can be solved optimally or approximately. We also undertake practical algorithm engineering, experimentation, and research in constraint and integer programming.
Supported by two prestigious research fellowships, we exploit mathematical structure in real-world datasets to develop provably efficient algorithms, including applications to livestock disease modelling. We also develop algorithms for counting and enumerating optimal or near-optimal solutions, with potential applications in more personalised screening, diagnosis and treatment for several common diseases.
A major focus is matching agents to resources, including resident doctors to hospitals and kidney patients to donors. Our kidney exchange algorithms have been used by NHS Blood and Transplant to identify over 2,200 living-donor transplants. We also study university course and project allocation.
In algorithmic game theory, we investigate equilibrium computation, auction design, congestion games, revenue optimisation and smoothed running-time analysis, combining theoretical complexity results with applied mechanism design.
Our constraint programming and algorithm engineering research includes the EPSRC-funded Glasgow Subgraph Solver, independently described as the world's fastest subgraph isomorphism solver. We also develop proof logging for constraint solvers, enabling formally verifiable evidence of solution correctness in a standard format.
Project Highlights
Beyond One Solution in Combinatorial Optimisation
Which characteristics should be used to determine whether a patient is offered routine cancer screening? Are there two or three qualitatively different types of heart failure? Which journeys should be forbidden to restrict the spread of an infectious disease?
Data-driven approaches to answering any of these questions - as well as many others in the field of digital health - typically involve searching for a single mathematical object which is optimal with respect to some criterion. For example, we might aim to partition patients into a fixed number of groups or "clusters" in a way that minimises the maximum "difference" in the characteristics of patients assigned to the same cluster.
However, there will often be many solutions that are equally good with respect to our chosen criterion, in which case it is misleading to consider just a single example: if there are many optimal ways to split our patient group into clusters, and there is little agreement between these optimal solutions about which patients belong to the same cluster, then we should not draw conclusions based on just a single optimal solution. It is therefore important to find out more about the whole set of good solutions.
Unfortunately, in most settings, even finding a single optimal solution is a very computationally challenging problem, and finding all good solutions (or even estimating how many of these there are) is even more difficult. This project aims to advance our understanding of how to design efficient algorithms that can (at least approximately) find all good solutions, count their number, or sample a good solution uniformly at random. To do this we will develop new techniques by drawing on two areas of computational complexity - parameterised complexity and approximate counting - whose intersection has not yet been properly explored. This will make it feasible to extract information about the entire space of good representative structures in many more settings, providing complete and fully explainable answers to our original healthcare-inspired questions as well as many others.
The Science of Solving Hard Subgraph Problems
Subgraph-finding problems involve identifying patterns in structured data. In theory these problems should be computationally hard for an algorithm to solve, but in practice intelligent constraint-based algorithms can quickly solve even large problems. This research will uses scientific (rather than purely mathematical) techniques to increase our understanding of this gap between theory and practice, and will allow us to design better algorithms in the future. The research is based upon analysing proof logs, which are a mathematical description of how an algorithm reached its answer.
KEPsoft-UK: New and Improved Algorithms for the UK Living Kidney Sharing Scheme
This project, funded by Kidney Research UK, involves the development of software for kidney exchange, which provides an additional option for patients who require a kidney transplant, and who have a willing but medically incompatible donor. Patients in this position may swap their donors to receive a compatible kidney, and a kidney exchange programme constructs an optimal set of exchanges based on a pool of patient-donor pairs.
The UK’s kidney exchange programme is called the UK Living Kidney Sharing Scheme (UKLKSS), and it is run by NHS Blood and Transplant. The purpose of this project is to develop new software for the UKLKSS, to allow for planned clinical innovations and other future enhancements.
The software will be designed with the requirements of the intended users at the forefront, taking into account feedback from the project’s Patient Advisory Group, and subjected to rigorous testing and validation in order to increase confidence in its correctness. The project will involve extending the existing KEPsoft platform, which has been developed using Python, Flask and other technologies.