Stochastic Minimum Norm Combinatorial Optimization

Title of the Talk: Stochastic Minimum Norm Combinatorial Optimization
Speakers: Dr. Sharat Ibrahimpur
Host Faculty: Dr.Rogers Mathew
Date: Dec 16, 2025
Time: 2:30 pm.

Abstract: Uncertainty is ubiquitous in real-world problems, which highlights a growing need for new mathematical and algorithmic tools for optimization under uncertainty. In this talk, I will describe a versatile model of stochastic combinatorial optimization with norm-based objectives, and discuss prominent hurdles that arise when devising algorithms for this model. In stochastic minimum-norm optimization, we have a generic combinatorial optimization problem in which the costs are random variables with known distributions, and feasible solutions induce multidimensional 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.

Speaker 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.