Algorithm Engineering for Scalable Data Reduction

现实世界中许多重要的优化问题都是NP难的：人们期望没有有效的(多项式时间)算法总是能找到最优解。然而，许多NP-Hard问题已经被证明是固定参数可处理的：只要某个问题参数很小，大输入问题就可以有效地且可证明是最优的。在过去的二十年里，对于各种各样的图问题，在设计和分析FPT算法方面取得了显著的进展。这些技术包括通过分而治之的方法将输入分解成块来解决问题的技术，或者应用技术在不改变答案的情况下减小问题的大小。然而，从实践的角度来看，这些理论上的算法思想却很少受到关注。很少有FPT算法在真实数据集上实现和测试，它们的实用潜力还远未被了解。通过以非平凡的方式应用来自FPT算法的技术，可以获得在NP-Hard问题的真实世界实例上执行得出奇地好的算法。本项目旨在弥合目前在FPT或核化方法中观察到的理论与实践之间的差距，以解决具有高度实际相关性的选定问题，特别是大规模应用，如在大规模物理模拟中经常使用的最小填充问题，或在地图标注或大规模物流应用中应用的加权独立集问题。在项目的每一点上，我们都会通过使用共享内存和分布式内存并行化将算法扩展到尽可能大的实例。这将导致算法更健壮、更灵活、产生更好的解决方案，并可扩展到比以前可能的更大的大规模并行机器和实例。此外，该项目旨在与来自不同应用领域的研究人员合作，将工程技术直接付诸实践。因此，该项目的目标是一种全面的算法工程研究方法，既包括优秀的算法研究，也包括解决具体应用。

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.