Optimization under Explorable Uncertainty

输入数据的不确定性甚至缺乏信息是现实生活中决策中无处不在的问题。可探索不确定性下的优化框架处理的是部分输入数据不确定，但可以通过一定代价的查询操作获得的问题。具有挑战性的问题是：应该查询哪些输入元素？需要多少信息才能达到一定的解决方案质量？这个项目的目标是开发新的技术来平衡数据探索的成本和解决方案质量的收益。我们的重点在于设计算法，在数学上保证得到的解的质量。我们通过量化并行决策的权力和限制以及通过研究超越经典最坏情况考虑的新模型来推进当前的技术水平。我们设想一个统一的方法来应对（随机）可探索的不确定性。我们还研究了最近的模型，如考虑易出错预测的学习增强算法。

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.