Lossy Kernelization

In this talk we propose a new framework for analyzing the performance of preprocessing algorithms. Our framework builds on the notion of kernelization from parametierized com-plexity. However, as opposed to the original notion of kernelization, our definitions combine nicely with approximation algorithms and heuristics. The key new definition is that of a polynomial size a-approximate kernel.