ERC Starting Grant for Bart Jansen: simplifying prior to solving

Four challenging projects for talented Assistant Professors of TU/e are awarded by the European Research Council (ERC) with individual Starting Grants of up to € 1.8 million each. One of them is Bart Jansen, Assistant Professor in the Algorithms & Visualization research group.

In our world of big data and theoretically intractable problems, it is becoming ever more important to simplify problems before algorithmically solving them, and Bart Jansen knows that well. “A suitable preprocessing step in which redundant constraints and variables are eliminated, has the potential to reduce computation times from days to seconds”, explains Jansen, “which inevitably calls for a thorough scientific understanding of the power and limitations of preprocessing procedures.”

With his Rigorous Search Space Reduction project (REDUCESEARCH), Jansen aims at re-shaping the theory of effective preprocessing. “Earlier research only considered how preprocessing can make the input to an algorithm smaller, without changing its answer”, says Jansen. “But to achieve the biggest speed-ups, preprocessing must reduce the exponential-size space of potential solutions that the algorithm searches through." The goal of the project is to develop a toolkit of algorithmic preprocessing techniques that reduce the search space, along with mathematical guarantees on the amount of search-space reduction that is achieved.