ERC Starting Grant for Bart Jansen
A European Research Council (ERC) Starting Grant worth up to € 1,473,020 has been awarded to Bart Jansen for his project 'Rigorous Search Space Reduction’. In the five-year project, two PhD students and five postdoc years will be involved.
Simplifying prior to solving: the REDUCESEARCH project
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 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. “