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.