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

从数据约简的意义上说，预处理对于np困难问题的实际解决至关重要。一个非常成功的例子是用于求解整数线性规划的商用工具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.