Optimization under explorable uncertainty: beyond the worst-case

Abstract

When solving optimization problems that arise in real-world applications, uncertainty in the input data and incomplete information are major challenges. Consider for example varying transportation times depending on traffic conditions or weather, variable parameters such as bandwidth and demands, or decentralized data that is updated infrequently. The three major mathematical models for uncertainty in optimization problems are online optimization, stochastic optimization and robust optimization. These models have in common that the uncertain information is usually either revealed passively over time or not at all. Optimization algorithms for problems in these models have to cope with this type of uncertainty and make decisions based on incomplete information. In particular, they do not have the option, not even at a cost, to actively obtain new information that helps to handle the optimization task at hand. This thesis considers the model of explorable uncertainty, where uncertain parts in the input of an optimization problem can be queried at a certain cost to reveal more information. The goal in explorable uncertainty is to design algorithms that query uncertain parameters until the revealed information is sufficient to determine an optimal solution to the underlying optimization problem, with the objective to minimize the query cost. So far, explorable uncertainty has mostly been studied in the adversarial setting, where we assume that query results are returned in a worst-case manner and analyze algorithms in terms of their competitive ratio. This setting however leads to strong lower bounds on the competitive ratio for several interesting problems and might be too pessimistic in many real world applications. Instead, this thesis considers several problems under explorable uncertainty and analyzes them in settings that go beyond the worst-case. In particular, we study a learning-augmented and a stochastic setting for problems under explorable uncertainty.