Algorithms for hard graph problems based on auxiliary data

点击翻译按钮获取中文摘要

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.