Combinatorial Optimization Reading Group - Sharat Ibrahimpur

Friday, October 28, 2022 12:00 pm - 12:00 pm EDT (GMT -04:00)

Title: Stochastic Minimum Norm Combinatorial Optimization

Speaker: Sharat Ibrahimpur
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.