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

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

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.