Beyond One Solution in Combinatorial Optimisation

组合优化中的超越一种解决方案

• 批准号: EP/V032305/1
• 负责人: Kitty Meeks
• 金额: $ 173.76万
• 依托单位: University of Glasgow
• 依托单位国家: 英国
• 项目类别: Fellowship
• 财政年份: 2021
• 资助国家: 英国
• 起止时间: 2021 至 无数据
• 项目状态: 未结题
• 来源: https://gtr.ukri.org/projects?ref=EP%2FV032305%2F1
• 关键词: Beyond; Solution; 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.

应使用哪些特征来确定患者是否接受常规癌症筛查？是否存在两种或三种性质不同的心力衰竭类型？应禁止哪些旅行以限制传染病的传播？回答这些问题以及数字健康领域的许多其他问题的数据驱动方法通常涉及搜索在某些标准方面最佳的单个数学对象。例如，我们的目标可能是将患者划分为固定数量的组或“簇”，以最小化分配到同一簇的患者特征的最大“差异”。但是，通常会有许多解决方案对于我们选择的标准来说同样好，在这种情况下，仅考虑一个示例会产生误导：如果有许多最佳方法将我们的患者组划分为簇，并且这些最佳解决方案之间几乎没有一致性 关于哪些患者属于同一簇，那么我们不应该仅根据单个最佳解决方案得出结论。因此，更多地了解整套好的解决方案非常重要。不幸的是，在大多数情况下，即使找到单个最佳解决方案，在计算上也是一个非常具有挑战性的问题，而找到所有好的解决方案（甚至估计其中有多少个）则更加困难。该项目旨在加深我们对如何设计有效算法的理解，这些算法可以（至少大约）找到所有好的解决方案，计算它们的数量，或者随机均匀地采样一个好的解决方案。为此，我们将利用计算复杂性的两个领域（参数化复杂性和近似计数）来开发新技术，这两个领域的交集尚未得到适当探索。这将使在更多环境中提取有关良好代表性结构的整个空间的信息成为可能，为我们最初的医疗保健启发问题以及许多其他问题提供完整且完全可解释的答案。

项目成果

Fair Division of a Graph into Compact Bundles

将图公平划分为紧凑束

• DOI: 10.24963/ijcai.2023/316
• 发表时间: 2023
• 作者: Madathil J

Counting Subgraphs in Somewhere Dense Graphs

计算密集图中的子图

• DOI: 10.4230/lipics.itcs.2023.27
• 发表时间: 2023
• 期刊: Leibniz International Proceedings in Informatics, LIPIcs
• 作者: Bressan M.