Department of InformaticsTheory of Efficient Algorithms

Algorithms are omnipresent in our modern life. They regulate the power usage of our mobile devices to make their batteries last longer. They analyze our movement patterns to provide traffic predictions when navigating urban traffic. Companies use them to automatically manage the inventory of warehouses or to plan efficient routes for delivery or pickup services.

These algorithms typically have to solve an underlying optimization problem. A major focus of our research group Theory of Efficient Algorithms is to systematically study what makes such optimization problems hard and how to find provably optimal or “good” solutions in an efficient way. We achieve this by identifying the intrinsic difficulties of the underlying optimization problem, abstracting from the real-world problem to isolate the aspects that make the problem difficult, and study structural properties of optimal or “good” solutions in this formal model.

Problems we study come from many different areas, including among others