Data reduction in parameterized algorithmics: New models and methods

DAMM项目旨在为NP-hard问题开发可证明的高效和有效的数据约简规则（问题核）。为此，我们考虑了新的核化概念，如图灵核或部分核，以及关于多元非标准参数的经典问题核（在这里，我们关注的问题来自新的应用领域，如机器学习或数据挖掘）。在有希望的情况下，我们希望根据经验评估我们的方法。与第一个项目提案相比，主要目标没有改变，但我们的重点转向了机器学习中的问题，如数据聚类。我们进一步关注启发式方法的分析，以及它们在数据缩减方面的潜力。此外，我们希望研究替代核化概念的效用，如多元问题核、弱问题核或部分问题核。特别是图灵核及其衍生物真表核是我们感兴趣的。到目前为止我们得到的结果表明，需要对问题核进行这样的松弛。此外，我们希望实现我们新开发的数据缩减，以便根据经验评估它们的性能。

The project DAMM aims at developing provably efficient and effective data reduction rules (problem kernels)for NP-hard problems. To this end, we consider new kernelization concepts such as Turing-kernels or partial kernels as well as classical problem kernels with respect to multivariate non-standard parameters (here, we focus problems from new application areas such as Machine Learning or Data Mining).In promising cases, we want to evaluate our methods empirically.In comparison to the first project proposal, the main goals did not change but our focus movedtowards problems from Machine Learning such as data clustering. We further concentrate on the analysisof heuristic approaches with respect to their potential for data reduction.Moreover, we want to investigate the utility of alternative kernelization concepts such as multivariate, weak or partial problem kernels. Especially Turing-kernels and their derivatives Truth-Table-kernels are of interest to us. The results we obtained so far indicate the need for such relaxations of problem kernels.Additionally, we want to implement our newly developed data reductions in order to evaluate their performance empirically.