Algorithms for hard graph problems based on auxiliary data

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

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.