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.
Short Bio:
Sharat Ibrahimpur is a postdoctoral researcher in the Computer Science department at ETH Zurich. Previously, he held postdoctoral positions at the University of Bonn and the London School of Economics. Sharat earned his M.Math. and Ph.D. degrees in Combinatorics and Optimization from the University of Waterloo. He completed his undergraduate degree in Applied Mathematics at the Indian Institute of Technology Roorkee. Sharat's research focuses on designing approximation algorithms for combinatorial optimization problems, with a special emphasis on optimization under uncertainty.
