Tutte Colloquium - Chaitanya Swamy
Title: Stochastic Minimum Norm Combinatorial Optimization
Speaker: | Chaitanya Swamy |
Affiliation: | University of Waterloo |
Location: | MC 5501 |
Abstract: We develop a framework for designing approximation algorithms for a wide class of (1-stage) stochastic-optimization problems with norm-based objective functions. We introduce the model of stochastic minimum-norm combinatorial optimization, wherein the costs involved are random variables with given distributions, and we are given a monotone, symmetric norm f. Each feasible solution induces a random multidimensional cost vector whose entries are independent random variables, and the goal is to find a solution that minimizes the expected f-norm of the induced cost vector. This is a very rich class of objectives, containing all l_p norms, as also Top-l norms (sum of l largest coordinates in absolute value), which enjoys various closure properties.