Christoph Grüne: Complexity and Algorithms in Optimization under Uncertainty

 

Robust problems are problems that are decided or optimized against some form of uncertainty. For this, finding measures of robustness to find solutions that deal with the given form of uncertainty is of interest.
On the other hand, online problems are decided or optimized while the instance is revealed piece-wise.
Both forms of problems may be modeled with the help of an adversary that controls either the uncertainty of the instance in robust problems or the piece-wise revelation of the instance in online problems. Among those may be problems with one player against an adversary (the “nature”), two players against each other or multiple player settings playing against or with each other.

The project will focus on different measures of robustness and different complexity viewpoints to analyze certain forms of problems. The complexity analysis may be based on classical complexity classes as well as parameterized complexity.