权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

Data reduction in parameterized algorithmics: New models and methods

参数化算法中的数据缩减：新模型和方法

基本信息

批准号：
218550609
负责人：
Professor Dr. Rolf Niedermeier (†)
金额：
--
依托单位：
Institut für Softwaretechnik und Theoretische Informatik
依托单位国家：
德国
项目类别：
Research Grants
财政年份：
2012
资助国家：
德国
起止时间：
2011-12-31 至 2017-12-31
项目状态：
已结题

来源：
https://gepris.dfg.de/gepris/projekt/218550609?language=en
关键词：
Data reduction parameterized algorithmics New

项目摘要

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.

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

项目成果

期刊论文数量（7）

专著数量（0）

科研奖励数量（0）

会议论文数量（0）

专利数量（0）

Exploiting hidden structure in selecting dimensions that distinguish vectors

DOI：
10.1016/j.jcss.2015.11.011
发表时间：
2015-12
期刊：
J. Comput. Syst. Sci.
影响因子：
0
作者：
Vincent Froese;René van Bevern;R. Niedermeier;Manuel Sorge
通讯作者：
Vincent Froese;René van Bevern;R. Niedermeier;Manuel Sorge

The Parameterized Complexity of the Minimum Shared Edges Problem

最小共享边问题的参数化复杂度

DOI：
10.4230/lipics.fsttcs.2015.448
发表时间：
2015
期刊：
ArXiv
影响因子：
0
作者：
T. Fluschnik;S. Kratsch;R. Niedermeier;M. Sorge
通讯作者：
M. Sorge

Finding Secluded Places of Special Interest in Graphs

在图表中寻找特别有趣的僻静地方

DOI：
10.4230/lipics.ipec.2016.5
发表时间：
2016
期刊：
ArXiv
影响因子：
0
作者：
R. Bevern;T. Fluschnik;G. B. Mertzios;H. Molter;M. Sorge;O. Suchý
通讯作者：
O. Suchý

Diminishable Parameterized Problems and Strict Polynomial Kernelization

DOI：
10.1007/978-3-319-94418-0_17
发表时间：
2016-11
期刊：
影响因子：
0
作者：
H. Fernau;T. Fluschnik;D. Hermelin;Andreas Krebs;Hendrik Molter;R. Niedermeier
通讯作者：
H. Fernau;T. Fluschnik;D. Hermelin;Andreas Krebs;Hendrik Molter;R. Niedermeier

Parameterized Aspects of Triangle Enumeration

三角形枚举的参数化方面