A single optimal solution to a data problem—like which patients to screen for cancer—can be dangerously misleading when many equally good solutions exist but disagree with each other. This project tackles a hidden flaw in how we use algorithms for healthcare decisions. When researchers search for the best way to cluster patients or restrict travel during an outbreak, they typically stop at one "optimal" answer. But if dozens of equally good answers exist, picking just one can lead to false confidence or biased conclusions. The problem is that finding even one optimal solution is computationally hard, and exploring all good solutions is far harder. The researchers will combine two branches of computational complexity—parameterised complexity and approximate counting—to design algorithms that can find, count, or randomly sample all good solutions, not just one. If successful, this would make it feasible to extract the full landscape of optimal answers in settings like cancer screening criteria, heart failure classification, and infectious disease control. The result would be more complete, explainable, and trustworthy data-driven decisions in digital health and beyond.
View original technical description
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.
Plain English summaries and category classifications on this site are generated by AI and may not perfectly reflect the original research.
Is something wrong? Let us know