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

Efficient preprocessing for hard problems: New techniques and tight models for data reduction

难题的高效预处理：数据缩减的新技术和严格模型

基本信息

批准号：
225019562
负责人：
Professor Dr. Stefan Kratsch
金额：
--
依托单位：
Institut für Informatik
依托单位国家：
德国
项目类别：
Independent Junior Research Groups
财政年份：
2012
资助国家：
德国
起止时间：
2011-12-31 至 2020-12-31
项目状态：
已结题

来源：
https://gepris.dfg.de/gepris/projekt/225019562?language=en
关键词：
Efficient preprocessing hard problems New

项目摘要

Preprocessing, in the sense of data reduction, is of fundamental importance for the practical solution of NP-hard problems. A very successful example is the commercial tool CPLEX for solving integer linear programs. It is known for its strong preprocessing. Nevertheless, for most of the time preprocessing has seen little theoretical study. One reason was that a robust theoretical model of preprocessing could not be found: A routine which shrinks every instance in polynomial time, could solve the whole problem in polynomial time (impossible unless P = NP). The notion of kernelization from the young area of parameterized complexity avoids this problem: A kernelization generates an equivalent instance whose size is bounded by a function in a parameter of the input; the size of the input is immaterial. Polynomial kernelizations, i.e., with output size polynomially bounded in the parameter, have turned into a vibrant field. The aim of this project is a fundamental deepening of the knowledge about preprocessing, starting at the notion of kernelization. On the one hand this includes a development of new techniques for kernelization and lower bounds. On the other hand it includes a research of other ways of modeling efficient preprocessing. The interplay of these two goals shall lead to precise results about preprocessing. One motivation comes from current techniques for lower bounds. Under complexity-theoretic assumptions, these techniques can be used to rule out the existence of polynomial kernelizations for certain problems. However, it has turned out, that this also rules out more general models of preprocessing for these problems; among them both practical as well as more theoretical models. Thus the techniques are not fully appropriate to answer the question of existence of efficient preprocessing. In PREMOD this thought shall be pursued. Some questions: Are there practical models which are not ruled out by current lower bound techniques? Can we develop more precise techniques for obtaining lower bounds? When can establish that a problem does not permit efficient preprocessing? A further motivation is the interest in the practicality of kernelization results. PREMOD shall contribute to this by researching stricter models for preprocessing as well as by experimental evaluation: Are existing kernelization results time- and space-efficiently implementable? Can we improve the choice of parameter, and obtain stronger results? How well is the interplay with approximation and heuristic algorithms? Are there more precise models for capturing the successful, simple, and local reduction rules from practice? Summarizing, PREMOD stands for the development of practically meaningful and theoretically sound models for preprocessing.

预处理，在这个意义上的数据减少，是非常重要的实际解决方案的NP难题。一个非常成功的例子是用于求解整数线性规划的商业工具CPLEX。它以其强大的预处理能力而闻名。然而，在大多数情况下，预处理很少有理论研究。一个原因是无法找到一个强大的预处理理论模型：一个在多项式时间内缩小每个实例的例程可以在多项式时间内解决整个问题（除非P = NP）。从参数化复杂性的年轻领域中的核化概念避免了这个问题：核化生成一个等价的实例，其大小由输入参数中的函数限制;输入的大小是无关紧要的。多项式核化，即，与输出大小多项式约束的参数，已经变成了一个充满活力的领域。这个项目的目的是从内核化的概念开始，从根本上深化关于预处理的知识。一方面，这包括核化和下界的新技术的发展。另一方面，研究了其他建模方法的有效预处理。这两个目标的相互作用将导致关于预处理的精确结果。一个动机来自当前的下界技术。在复杂性理论的假设下，这些技术可以用来排除某些问题的多项式核化的存在。然而，事实证明，这也排除了更一般的模型，这些问题的预处理，其中既有实际的，以及更多的理论模型。因此，这些技术并不完全适合回答有效预处理存在的问题。在PREMOD中，应遵循这一思想。一些问题：有没有实用的模型，不排除由目前的下限技术？我们能开发出更精确的技术来获得下界吗？什么时候可以确定一个问题不允许有效的预处理？另一个动机是对核化结果的实用性的兴趣。PREMOD将通过研究更严格的预处理模型以及实验评估来为此做出贡献：现有的内核化结果是否可以在时间和空间上有效地实现？我们能否改进参数的选择，并获得更强的结果？近似算法和启发式算法的相互作用如何？有没有更精确的模型来从实践中捕捉成功的、简单的和局部的归约规则？总而言之，PREMOD代表开发有实际意义和理论上合理的预处理模型。