Optimization under Uncertainty
The focus of my research as a member of the UnRAVeL research training group is to study algorithms and complexity of robust optimization problems.
Traditional methods for optimization have the problem that they find solutions that are optimal for one specific scenario, but which are very susceptible to variations in the input. This is a problem because in real world optimization problems often decisions have to be made before all parameters of the instance are completely known. Real world parameters might be uncertain in the planing and optimization process and their real value only becomes apparent later. This leads to the problem of finding robust solutions that optimize the worst case performance considering all possible realizations i.e. solutions that minimize the worst possible regret.
Because of this additional quantor in the problem definition finding those solutions is usually a lot harder than the original optimization problem. They often lie in complexity classes beyond NP and are hard for those classes. I try to pinpoint the complexity of those robust optimization problems.
Another area of my research is the approximation of robust optimization problems. I either try to find algorithms that find solutions which are provably close to the optimal solution but have polynomial running time or I prove that existence of such an approximation algorithm would have complexity theoretic consequences which are generally believed to be false.
Another way of looking at robust optimization problem is as a two step process. First an agent chooses a solution and then the scenario is picked by an adversary. Other things I am interested in other than determining the difficulty of finding a strategy for the agent is finding a strategy for the adversary. Symmetrically we can ask questions about approximability of the adversary.