Title: Stochastic Minimum Norm Combinatorial Optimization
| Speaker: | Sharat Ibrahimpur |
| Affiliation: | |
| Location: | MC 6029 or contact Rian Neogi for Zoom link |
Abstract: In this work, we introduce and study stochastic minimum-norm optimization. We have an underlying combinatorial optimization problem where the costs involved are random variables with given distributions; each feasible solution induces a random multidimensional cost vector. The goal is to find a solution that minimizes the expected norm of the induced cost vector, for a given monotone, symmetric norm. We give a framework for designing approximation algorithms for stochastic minimum-norm optimization and apply it to give approximation algorithms for stochastic minimum-norm versions of load balancing and spanning tree problems.
Joint work with Chaitanya Swamy. A full version of our results can be found in the speaker's PhD thesis with the same title.