New Horizons in Multivariate Preprocessing (MULTIPROCESS)

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

Data preprocessing or data compression is a ubiquitous strategy to cope with computational hardness in various real world applications. The goal here is to efficiently compute a succinct representation of the original data with only a small loss in the accuracy of the information represented within it. This is achieved through various steps such as simplifying the structure of the input, reducing the size or dimension, removing redundant constraints and so on.The widespread recognition of the importance of preprocessing algorithms in practice has motivated the challenging task of developing mathematical frameworks within which it is possible to conduct rigorous analysis, provide performance guarantees and compare the quality of various preprocessing algorithms proposed for specific computational problems. A partial answer to this challenge was provided in the area of parameterized complexity (or multivariate complexity) through the framework of kernels. This framework has lead to a vibrant new subfield of algorithmics -- Kernelization. The field of kernelization has turned out to be a resounding success over the last two decades as far as the analysis and understanding of 'lossless' preprocessing for NP-hard (computational problems that are not expected to have theoretically efficient, i.e., so called polynomial-time algorithms) decision problems is concerned. However, in practice, preprocessing is heavily used for large data sets of problems that have theoretically efficient (polynomial-time) algorithms as well as for NP-hard problems where one wants to optimize some objective function over the input data. In these situations, the framework of kernelization falls woefully short and does not combine well with approximation algorithms or heuristics. This proposal aims to make major advances in the mathematical theory of preprocessing by delivering new formulations of efficient preprocessing that overcome the aforementioned fundamental limitations that plague the classic theory of polynomial-time preprocessing. This project will lead to novel preprocessing heuristics and analyses for basic computational problems and extend the scope of rigorous preprocessing analysis to high-impact big data paradigms such as streaming algorithms. This will be achieved by delivering new preprocessing design techniques as well as new mathematical machinery that allows one to formally characterize the limitations of preprocessing for various problems. This project will bring about a paradigm shift by laying the foundations for a new theory of preprocessing that will be able to abstract and unify all efficient preprocessing. This is but the beginning of a timely journey into a mostly unexplored universe teeming with possibilities and undiscovered connections between diverse subfields of computer science.