Simplifying prior to solving

Prijs: ERCStartingWetenschappelijk


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.
Mate van erkenningInternationaal
Toekennende organisatieEuropean Research Council