| Title | : | Approximation Algorithms for Optimization under Uncertainty |
| Speaker | : | Sharat Ibrahimpur (ETH Zurich) |
| Details | : | Mon, 5 Jan, 2026 11:30 AM @ SSB 334 |
| Abstract: | : | Uncertainty is ubiquitous in real-world problems, highlighting a growing need for new mathematical and algorithmic tools for optimization under uncertainty. In this talk, I will discuss two prominent hurdles that arise in stochastic combinatorial optimization, along with recent advances that address these challenges.
The first setting considers a generic combinatorial optimization problem in which the costs are random variables with known distributions, and feasible solutions induce multi-dimensional cost vectors. The algorithmic goal is to compute an oblivious solution that minimizes the expected norm of the associated cost vector for a given monotone, symmetric norm. One can show that optimizing the norm of the expected cost vector may yield solutions whose approximation quality degrades with the dimensionality of the problem. I will present a powerful theorem, dubbed approximate stochastic majorization, that enables constant-factor approximations for norm-based objectives across a wide class of combinatorial optimization problems. I will then turn to stochastic decision environments where forgoing adaptivity for simplicity or analytical convenience can lead to poor approximation guarantees. I will illustrate this through a novel variant of two-stage stochastic load balancing that enables a quantitative trade-off between the practical benefits of non-adaptive algorithms and their performance limitations. I will present a striking power-of-two-choices result for stochastic load balancing, showing that constant-factor approximations are achievable with limited adaptivity relative to the omniscient and adaptive optimums. |
