• Preprocessing

    • Rigorous Theory of Preprocessing is the project funded by the European Research Council (ERC) via the Advanced Investigator Grant scheme. The project duration is five years, starting from April 2011. The main research goal of the project is the quest for rigorous mathematical theory explaining the power and failure of heuristics. The incapability of current computational models to explain the success of heuristic algorithms in practical computing is the subject of wide discussion for more than four decades. Within this project we study of a large family of heuristics: Preprocessing (data reduction or kernelization). Preprocessing is a reduction of the problem to a simpler one and this is the type of algorithms used in almost every application. The project aims to develop new theory of polynomial time compressibility. Understanding the origin of compressibility will serve to build more powerful heuristic algorithms, as well as to explain the behaviour of preprocessing.

  • Positions

    • There are several research positions at postdoctoral level associated with this project. Please contact Fedor Fomin for details.

  • Events

    • TW(BGO)-11 +++ WORKER 2011

  • Links

    • Article about Kernelization in Wikipedia +++ WORKER is a workshop on Kernelization

  • Selected Publications

    • to appear

    [Top of page]