Data reduction in parameterized algorithmics: New models and methods

• Applicant: Professor Dr. Rolf Niedermeier (†)
• Subject Area: Theoretical Computer Science
• Term: from 2012 to 2018
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 218550609

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.

• DFG Programme: Research Grants