Algorithm Engineering for Scalable Data Reduction

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

Many important real-world optimization problems are NP-hard: it is expected that no efficient (polynomial-time) algorithm exists that always finds an optimal solution. However, many NP-hard problems have been shown to be fixed-parameter tractable (FPT): large inputs can be solved efficiently and provably optimally, as long as some problem parameter is small. Over the last two decades, significant advances have been made in the design and analysis of FPT algorithms for a wide variety of graph problems. These include techniques that decompose the input into pieces to solve the problem with a divide-and-conquer approach, or the application of techniques to reduce the problem size without changing the answer. However, these theoretical algorithmic ideas have received very little attention from the practical perspective. Few FPT algorithms are implemented and tested on real datasets, and their practical potential is far from understood. By applying techniques from FPT algorithms in nontrivial ways, algorithms can be obtained that perform surprisingly well on real-world instances for NP-hard problems. This project aims to bridge the gap between theory and practice currently observed in FPT or kernelization approaches for selected problems with high practical relevance, in particular for massive scale applications such as the minimum fill-in problem that is frequently used in large scale physics simulations or the weighted independent set problem that has applications in map labelling or in large scale logistics applications. At every point in the project we will scale the algorithms to the largest instances possible by using shared-memory and distributed-memory parallelization. This will result in algorithms that will be more robust, more flexible, produce better solutions, and scale to massively parallel machines and instances much larger than previously possible. Additionally, the project aims to cooperate with researchers from different fields of application to put the engineered techniques directly into practice. Thus, the goal of the project is a comprehensive approach to algorithm engineering research which involves both excellent algorithms research as well as solving concrete applications.