Combinatorial Optimization Reading Group - Sharat Ibrahimpur

Title: Stochastic Minimum Norm Combinatorial Optimization

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.