White Rose FGAA
The aim of the project is to initiate a long-term collaboration (Foundations and Guarantees for Algorithms and AI)
providing new algorithms for big data sets and networks that are extremely fast and come with accuracy and performance guarantees.
Algorithms (computing instructions) run daily-life smart devices, online shopping and banking, journey planning and navigation, social networks, aircraft, as well as applications in cyber-security, medical diagnosis, autonomous vehicles, and in research.
For example, the classical “Travelling Salesperson Problem” asks for a shortest route connecting a number of cities. This problem is computationally hard. Even with a modest
number of cities the fastest algorithm can take years to compute an optimal route in the worst case.
Nonetheless problems like this have to be solved in practice. Nowadays, route planning is increasingly complex, with choice regarding means of transport, cost and transfer times, live
traffic updates and much more. Calculating routes that are guaranteed to be of high quality within milliseconds can save time, money, energy and even lives in an emergency. Particularly in the presence of big data, the majority of algorithms used do not come with any
guarantees.
This project aims to provide algorithms for many computational problems (e.g. all problems that can be expressed in a common logic), with guarantees regarding the quality of the computed answer, the running time and energy consumption, as well as reliability of control algorithms (trust, insurability). Since we cannot expect to solve hard problems both optimally and quickly, this project will exploit the structure of real-world big data sets and identify trade-offs (approximation, high probability versus computation time). Bringing together researchers with track records in diverse approaches to the challenge. The project proposes a novel and unique combination of classical and recent methods (including sublinear time algorithms, local, distributed, randomised, parametrised, machine learning) from the areas of Theoretical Computer Science (with mathematical proofs providing guarantees), Discrete Algorithms, Logic and AI.
Wide applicability will be given by a general mathematical setting. Applications include network analysis and routing, clustering, mage processing, approximate database querying, and optimisation, which will pipeline into innovation.
Lead Academic at lead university
Dr Isolde Adler University of Leeds
Lead Academics at other universities
Dr Sebastian Ordyniak University of Sheffield
Dr James Cussens University of York
Other Academics associated with this project
Dr Haiko Muller University of Leeds
Dr Felix Salfelder University of Leeds,
Dr Pan Peng University of Sheffield
Dr Peter Nightingale University of York
