ERC Starting Grant of DKK 11 million to computer scientist Lars Rohwedder

Computer scientist Lars Rohwedder from the Department of Mathematics and Computer Science has received a grant from the European Research Council totaling €1,498,648 — equivalent to just over 11 million Danish kroner.

This is a Starting Grant, awarded to young, talented researchers who aim to build their own research team.

With this grant, Lars will establish his own research group to improve algorithms for optimization problems. These are problems like: How do I cut materials to the right sizes, minimizing the waste? Or: How do I balance the workload of different servers in a data center?

One of the most common approaches to these problems is linear programming, a mathematical language that allows us to describe problems precisely to a software program, which then searches for a solution. The language is a variant of the systems of equations that many of us know from school.

For example, we could ask the software to find binary variables x, y, z that satisfy 2 x - y = z + 1. The two solutions are x = 1, y = 1, z = 0 and x = 1, y = 0, z = 1. But how can software systematically search through the billions of options in a larger system? To software, such a linear program looks like a high-dimensional polyhedron, a mathematical object with flat faces, sharp corners and straight edges. From studying polyhedra, we can improve algorithms.

Lars is particularly interested in applying this paradigm to so-called parameterized algorithms, a direction that came out of the need to tailor or analyze algorithms for specific data set characteristics. He believes that the combination of polyhedral methods and parameterized algorithms is currently underdeveloped and that advancing it could be the key to better algorithms for some of the most challenging problems.