Algorithm Engineering for Scalable Data Reduction

可扩展数据缩减的算法工程

• 批准号: 471903337
• 负责人: Professor Dr. Christian Schulz
• 金额: --
• 依托单位: Institut für Informatik
• 依托单位国家: 德国
• 项目类别: Research Grants
• 资助国家: 德国
• 项目状态: 未结题
• 来源: https://gepris.dfg.de/gepris/projekt/471903337?language=en
• 关键词: Algorithm; Engineering; 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.

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