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

Trade-offs in Parameterized Data Reduction

参数化数据缩减的权衡

基本信息

批准号：
389085303
负责人：
Professor Dr. Rolf Niedermeier (†)
金额：
--
依托单位：
Russian Foundation for Basic Research
依托单位国家：
德国
项目类别：
Research Grants
财政年份：
2017
资助国家：
德国
起止时间：
2016-12-31 至 2021-12-31
项目状态：
已结题

来源：
https://gepris.dfg.de/gepris/projekt/389085303?language=en
关键词：
Trade offs Parameterized Data Reduction

项目摘要

Kernelization is arguably one of the major contributions of parameterized complexity analysis to algorithm design: for a given instance of a (typically NP-hard) problem, one computes in polynomial time an equivalent instance whose size can be upper-bounded by a function only depending on some parameter (which measures some (structural) property of the input).Many kernelizations are composed of data reduction rules that are applied as long as applicable.In this project, based on many years of experience with various facets of kernelization, we plan to further push the development of new aspects of kernelization, particularly focussing on various trade-off effects.In particular, we are interested in trade-offs of efficient kernelization time and effective kernel size with a number of quality measures for kernels.So we are interested in Pareto-optimal kernels, then making use of "chaining effects" by executing one kernelization after another.Further, we plan to systematically explore concepts such as partial kernelization, approximative kernelization, randomized kernelization, Turing kernelization etc., all with the ultimate goal to trade better running time and/or kernel size against some relaxation of the kernel concept.Doing so, we plan to contribute both theoretically (including new frameworks and lower bounds) and practically (up to algorithm engineering).Although our focus is on NP-hard problems, we also include polynomial-time solvable problems in our considerations.

核化可以说是参数化复杂性分析对算法设计的主要贡献之一：对于给定的（典型的NP难）问题，在多项式时间内计算一个等价的实例，其大小可以由一个仅取决于某个参数的函数来限定（它测量输入的某些（结构）属性）。许多内核化都是由数据简化规则组成的，只要适用，就会应用这些规则。在这个项目中，基于多年的内核化各个方面的经验，我们计划进一步推动核化新方面的发展，特别是关注各种权衡效应。特别是，我们对有效核化时间和有效核大小与核的许多质量度量的权衡感兴趣。因此，我们对Pareto最优核感兴趣，然后通过执行一个又一个核化来利用“链式效应”。此外，我们计划系统地探索部分核化，近似核化，随机核化，图灵核化等概念，所有的最终目标都是以更好的运行时间和/或内核大小来换取内核概念的放松。这样做，我们计划在理论上（包括新的框架和下限）和实践上（直到算法工程）做出贡献。虽然我们的重点是NP难问题，但我们也考虑多项式时间可解问题。