Algorithms under Uncertainty

Franziska Eberle & Nicole Megow

Many powerful optimization methods assume that all input data is known in advance, but this is rarely true in modern applications such as logistics, production planning, cloud computing, networking, and energy-aware scheduling. In these settings, processing times, demands, transit times, bandwidth, or energy requirements may be unknown, uncertain, or rapidly changing. This course, introduces algorithmic models and techniques for dealing with such incomplete information. We will study online optimization, where decisions must be made immediately as input arrives, as well as selected stochastic models that use historical data to reason about uncertainty. A particular focus will be on recent approaches that combine classical algorithm design with machine learning, using predictions to improve performance while preserving rigorous guarantees even when these predictions are inaccurate.