Optimization under Explorable Uncertainty

• Applicant: Professorin Dr. Nicole Megow
• Subject Area: Theoretical Computer Science
• Term: since 2023
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 517912373

Uncertainty in the input data or even lack of information are an omnipresent issue in real-life decision making. The framework of optimization under explorable uncertainty deals with problems where part of the input data is uncertain but can be obtained by a query operation at a certain cost. Challenging questions are: Which input elements shall be queried? How much information is required to achieve a certain solution quality? The goal of this project is to develop new techniques for balancing the cost for data exploration and the benefit for the solution quality. Our focus lies on designing algorithms with mathematical guarantees on the quality of obtained solutions. We advance the state of the art by quantifying the power and limits of parallel decision-making and by studying new models beyond the classical worst-case considerations. We envision a unified methodology for coping with (stochastic) explorable uncertainty. We investigate also recent models such as learning-augmented algorithms taking error-prone predictions into account.

• DFG Programme: Research Grants