Abstract
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.
During the talk we will put up the framework and exemplify its utility via several examples.