Algorithms for hard graph problems based on auxiliary data

基于辅助数据的硬图问题算法

• 批准号: FT140100048
• 负责人: Prof Serge Gaspers
• 金额: $ 49.05万
• 依托单位: The University of New South Wales
• 依托单位国家: 澳大利亚
• 项目类别: ARC Future Fellowships
• 财政年份: 2015
• 资助国家: 澳大利亚
• 起止时间: 2015-06-01 至 2019-05-31
• 项目状态: 已结题
• 来源: https://dataportal.arc.gov.au/RGS/Web/Grants/FT140100048
• 关键词: Algorithms; hard; graph; problems; based

When solving computational problems, algorithms usually access only the data that is absolutely necessary to define the problem. However, much more data is often readily available. Especially for important or slowly evolving data, such as road networks, social graphs, company rankings, or molecules, more and more auxiliary data becomes available through computational processes, sensors, and simple user entries. This auxiliary data can greatly speed up an algorithm and improve its accuracy. This project aims to design improved algorithms that harness auxiliary data to solve selected high-impact NP-hard graph problems, and will build a new empowering theory to discern when auxiliary data can be used to improve algorithms.

在解决计算问题时，算法通常只访问定义问题所必需的数据。然而，更多的数据往往是现成的。特别是对于重要或缓慢发展的数据，如道路网络，社交图谱，公司排名或分子，越来越多的辅助数据通过计算过程，传感器和简单的用户输入变得可用。这些辅助数据可以大大加快算法的速度并提高其准确性。该项目旨在设计改进的算法，利用辅助数据来解决选定的高影响力NP-难图问题，并将建立一个新的授权理论来识别何时可以使用辅助数据来改进算法。