Unlocking the potential for linear and discrete optimisation in knot theory and computational topology

释放结理论和计算拓扑中线性和离散优化的潜力

• 批准号: DP140104246
• 负责人: Prof Benjamin Burton
• 金额: $ 24.44万
• 依托单位: The University of Queensland
• 依托单位国家: 澳大利亚
• 项目类别: Discovery Projects
• 财政年份: 2014
• 资助国家: 澳大利亚
• 起止时间: 2014-01-01 至 2017-12-31
• 项目状态: 已结题
• 来源: https://dataportal.arc.gov.au/RGS/Web/Grants/DP140104246
• 关键词: Unlocking; potential; linear; discrete; optimisation

Computational topology is a young, energetic field that uses computers to solve complex geometric problems, such as whether a loop of string is tangled. Such computations are becoming increasingly important in mathematics, and applications span biology, physics and information sciences, however many core problems in the field remain intractable for all but the simplest cases. This project unites geometric techniques with powerful methods from operations research, such as linear and discrete optimisation, to build fast, powerful tools that can for the first time systematically solve large topological problems. Theoretically, this project has significant impact on the famous open problem of detecting knottedness in fast polynomial time.

计算拓扑是一个年轻而充满活力的领域，它使用计算机来解决复杂的几何问题，例如绳环是否缠结。此类计算在数学中变得越来越重要，其应用涵盖生物学、物理学和信息科学，然而，除了最简单的情况外，该领域的许多核心问题仍然难以解决。该项目将几何技术与运筹学的强大方法（例如线性和离散优化）结合起来，构建快速、强大的工具，首次系统地解决大型拓扑问题。从理论上讲，该项目对快速多项式时间内检测结点的著名开放问题具有重大影响。