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.