Algorithm Engineering for NP-hard Problems: Parameterized Algorithms versus Established Techniques

许多来自不同应用领域的组合问题，如生物学、运筹学或数据挖掘，都是np困难的。在实践中，主要采用启发式或数学规划（ILPs）来解决这类问题；然而，这些通常缺乏对解决方案质量或运行时间的保证。参数化算法是最近出现的一种方法，它试图在可证明的有限时间内最优地解决实践中的问题。尽管在理论和领域上有很大的进展，有明确的适用性声明，但很少有实际数据的实现和实验工作，导致实际可部署的软件。在本项目中，首先基于参数化算法开发求解np困难问题的新方法；然后将执行这些方法并与传统技术方法进行比较，以便得出一般性建议。此外，参数化技术将用于改进启发式和ILP方法。通过这种方式，将检查参数化算法在多大程度上可以坚持提供实际相关的解决方法。为此，还将制定一般原则和说明，说明如何使用参数化算法的方法来解决难题。

Many combinatorial problems from diverse application areas such as biology, operations research, or data mining, are NP-hard. In practice, mainly heuristics or mathematical programming (ILPs) are employed for such problems; however, these typically lack guarantees on solution quality or guarantees on running time. Parameterized algorithms are a recent approach that tries to solve problems from practice optimally in provably bounded time. Although there is much progress in the theory and the field has the explicit claim of applicability, there are few works on implementation and experiments with real-world data that lead to practically deployable software. In this project, first based on parameterized algorithmics new methods for solving NP-hard problems will be developed; these will then be implemented and compared to conventional technique approaches, in order to reach generel recommendations. Further, parameterized techniques will be used to improve heuristics and ILP approaches. In this way, it will be examined how far parameterized algorithmics can hold up to the claim of delivering practically relevant solution methods. For this, also general principles and instructions will be developed that show how to attack a hard problem with the methods of parameterized algorithmics.