Title: Optimization under Explorable Uncertainty: Adversarial and Stochastic Models
Abstract: In the traditional frameworks for optimization under uncertainty, an algorithm has to accept the incompleteness of input data. Clearly, more information or even knowing the exact data would allow for significantly better solutions. How much more information suffices for obtaining a certain solution quality? Which information shall be retrieved? Explorable uncertainty is a framework in which parts of the input data are initially unknown, but can be obtained at a certain cost using queries. An algorithm can make queries until it has obtained sufficient information to solve a given problem. The challenge lies in balancing the cost for querying and the impact on the solution quality.
In this talk, I will give an overview on the field of explorable uncertainty with a focus on combinatorial optimization problems. I will include problems such as finding a minimum spanning tree in a graph of uncertain edge cost, finding the minimal elements in intersecting sets, and finding a set of minimum total value. The latter can be seen as a subproblem of more complex problem such as a solving a knapsack or matching problem under explorable uncertainty. I will discuss an adversarial online model and recent advances on a stochastic variant.
Bio: Nicole Megow is a professor at the University of Bremen, Germany. She obtained her PhD in Mathematics from TU Berlin in 2006. She spent some time as a postdoc at the Max Planck Institute for Informatics, Saarbrücken, headed a Junior Research Group at TU Berlin, and was an assistant professor for Discrete Mathematics at TU Munich. Since 2016, she has held the Chair for Combinatorial Optimization in the Faculty of Mathematics and Computer Science at the University of Bremen. She is a member of the Data Science Center.
Nicole Megow's research is focused on the design and analysis of efficient algorithms for combinatorial optimization problems. Her research is focused on understanding how to cope with incomplete or imperfect information (uncertainty of problem data, complete lack of information, untrusted predictions) when solving such problems.
