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.
Our chief contribution is a framework for designing approximation algorithms for stochastic minimum-norm optimization, based on two key components:
(i) A reduction showing that one can control the expected f-norm by simultaneously controlling a (small) collection of expected Top-l norms; and
(ii) Showing how to tackle the minimization of a single expected Top-l-norm by leveraging techniques used to deal with minimizing the expected maximum, circumventing the difficulties posed by the non-separable nature of Top-l norms.
We apply our framework to obtain strong approximation guarantees for two concrete problem settings: (1) stochastic load balancing, wherein jobs have random processing times and the induced cost vector is the machine-load vector; and (2) stochastic spanning tree, where edges have stochastic weights and the cost vector consists of the edge-weight variables of edges in the spanning tree returned.
This is joint work with Sharat Ibrahimpur.