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

点击翻译按钮获取中文摘要

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.