Combinatorial optimization is a classic field, whose results are applied in numerous domains, including logistics, telecommunication, production scheduling, and health care. Many of the problems arising in this field are computationally hard (often NP-hard) to solve exactly. Therefore, approximation algorithms, i.e., efficient algorithms with provable performance guarantees, have been extensively investigated.

An aspect that is very relevant in practice, but which has only been addressed unsatisfactorily thus far, is uncertainty in the input. Stochastic models for uncertainty, where there is some probabilistic information about the uncertain parameters, are arguably the most common approach for algorithms under uncertainty. The main question that this seminar addresses is: Can we approximate (or even compute exactly) the best strategy to interact with stochastic uncertainty?

Such a strategy may adapt when uncertainty gets resolved. An additional, structural, question is the question for the adaptivity gap , i.e., to what degree adaptivity helps in the objective function. Existing and envisioned tools comprise (but are not limited to) probabilistic approaches (concentration inequalities, martingales, etc.), linear or convex optimization, rounding techniques, and dynamic programming.

In this Dagstuhl Seminar, we are gathering several researchers from different communities (approximation algorithms, algorithmic game theory, operations research, online algorithms, learning theory) that have been interested in this or related questions from different angles. The goal is developing new techniques, identifying new models and directions, and solving some of the many open problems related to the above question.

The specific problems considered in this seminar are stochastic function-evaluation problems, stochastic probing and selection problems, stochastic scheduling, online stochastic problems, and related problems. We also plan to investigate aspects such as sample-complexity bounds, approximate solutions with low regret, and relaxing the common independence assumption.

Creative Commons BY 4.0

Lisa Hellerstein, Viswanath Nagarajan, and Kevin Schewior