Fall 2017

LPs and Convex Programming Relaxations and Rounding for Stochastic Problems

Monday, Sep. 11, 2017 11:30 am12:00 pm

Add to Calendar

We will survey some ways that linear programming relaxations can capture optimal strategies in (discrete) stochastic optimization
problems. These problems are often NP-hard or worse, and we will discuss techniques used to develop approximation algorithms for
them. Examples include  stochastic knapsack and some budgeted multi-armed bandit problems.