EPSRC logo

Details of Grant 

EPSRC Reference: EP/V032305/1
Title: Beyond One Solution in Combinatorial Optimisation
Principal Investigator: Meeks, Dr K
Other Investigators:
Jani, Dr B Enright, Dr J Anderson, Dr C
Researcher Co-Investigators:
Project Partners:
Department: School of Computing Science
Organisation: University of Glasgow
Scheme: EPSRC Fellowship
Starts: 01 October 2021 Ends: 31 March 2030 Value (£): 1,363,670
EPSRC Research Topic Classifications:
Fundamentals of Computing Logic & Combinatorics
EPSRC Industrial Sector Classifications:
No relevance to Underpinning Sectors
Related Grants:
Panel History:
Panel DatePanel NameOutcome
24 Feb 2021 EPSRC ICT and DE Fellowship Interviews 24 February 2021 Announced
27 Jan 2021 EPSRC ICT Prioritisation Panel January 2021 Announced
Summary on Grant Application Form
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.

Key Findings
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
Potential use in non-academic contexts
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
Description This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
Date Materialised
Sectors submitted by the Researcher
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
Project URL:  
Further Information:  
Organisation Website: http://www.gla.ac.uk