Parameterized Algorithmics in Computational Sustainability (PACS)

• Applicant: Dr. Till Fluschnik
• Subject Area: Theoretical Computer Science
• Term: since 2023
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 522475669

In a nutshell, computational sustainability aims to identify, formalize, and solve computational problems arising when trying to secure that the earth’s biosphere and human civilization can co-exist in the long run. The contribution of theoretical computer science, in particular the field of algorithms and complexity, can be very valuable but is currently yet fairly limited. Given the many-faceted nature of computational sustainability problems, which are typically computationally hard, and of the corresponding real-world data, we want to pioneer systematic parameterized algorithmics approaches to selected computation-intensive discrete and combinatorial problems from computational sustainability in order to find optimal solutions (in the sense of exact algorithms). Many natural problems in this context ‘carry’ (explicitly or implicitly) specific structure that one may capture with corresponding parameterizations, which are to be exploited in corresponding parameterized algorithms (including polynomial-time data reduction). Given the success stories of parameterized algorithmics in diverse application domains such as bioinformatics or computational social choice, methods and tools from parameterized algorithmics have the clear potential to make a valuable contribution to efficiently solve relevant problems from computational sustainability. These problems may come in different ‘maturity levels’ when seen through algorithmic glasses. More specifically, on the one extreme end, the computational problem at hand may be unknown, while on the other extreme end, the mathematical model is already provided and ‘only’ a parameterized view on the problem is missing. We want to target the range spanned by these to ends. As a start, we already spotted and modeled problems from different levels related to the topics 'adaption to extreme events', 'biodiversity', 'public transport', and 'vehicle sharing'.

• DFG Programme: Research Grants