Combinatorial and Discrete Optimization

In combinatorial optimization one deals with solution methods for problems which usually have a problem-specific combinatorial structure of the solution set. A classical example is the shortest path problem. Here, a graph is given and the solution set is implicitly described by the set of paths connecting a given starting node to a final node. Often the respective optimization problems are motivated by a concrete application from practice.

In the research group, we conduct research on both exact and approximate methods that compute optimal solutions or those with a guaranteed goodness in polynomial time.

Algorithmic Game Theory

Non-cooperative and cooperative game theory offer mathematical descriptions of decentrally organized systems (e.g., transportation systems and the Internet); a fundamental concept of non-cooperative game theory is, for example, the so-called Nash equilibrium. A central research focus of the group is an algorithmic view on the topics existence of equilibria, computational complexity of equilibria, and quality of equilibria.

Bilevel Optimization

Optimization of systems characterized by equilibrium conditions falls into the field of bilevel optimization. Problems of this class are quite difficult to solve, since they are usually non-convex and also non-differentiable. In this area, work is done on optimal network design under equilibrium conditions, design of combinatorial auctions, and design of optimal cost distributions in networks. In particular, the group works on the optimization of traffic light circuits, the use of navigation devices, and optimal network design (taking into account user equilibria).