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

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

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.