CS 295-9 - Stochastic Optimization

Course Information

Instructor: Eli Upfal (eli@cs.brown.edu), CIT 473, x37601
Lecture Place and Hours: CIT 506 , T.,Th. 1:00 - 2:20 pm

Outline

This advanced graduate course/seminar will focus on optimization under uncertainty, or optimization problems where some of the constrains include random (stochastic) components. Most practical optimization problems are stochastic (subject to future market conditions, weather, faults, etc.), and there has been substantial research (both theoretical and experimental) in efficient solution for such problems. We'll read and discuss some of the recent works in this area.

Papers :

R. Ravi, and A. Sinha
Hedging Uncertainty

N. Immorlica, D. Karger, M. Minkoff, and V. Mirrokni
On the Costs and Benefits of Procrastination: Approximation Algorithms for Stochastic Combinatorial Optimization Problems

B. Dean, M. Goemans, and J. Vondrak
Approximating the Stochastic Knapsack Problem: The Benefit of Adaptivity

A. Kleywegt, A. Shapiro, A. T. Homem-de-Mello
The Sample Average Approximation Method for Stochastic Discrete Optimization

S. Ahmed, and A. Shapiro
The Sample Average Approximation Method for Stochastic Programs with Integer Recourse

H. Yaman, O. Ekin Karasan, and M. C. Pinar
The Robust Spanning Tree Problem with Interval Data

I. D. Aron, P. Van Hentenryck
On the Complexity of the Robust Spanning Tree Problem with Interval Data

R. Bent, P. Van Hentenryck
Scenario-Based Planning for Partially Dynamic Vehicle Routing with Stochastic Customers

R. Bent, P. Van Hentenryck
Regrets Only! Online Stochastic Optimization under Time Constraints

R. Bent, P. Van Hentenryck
Online Stochastic and Robust Optimization

A. Goel, P. Indyk
Stochastic Load Balancing and Related Problems

D. Bertsimas, A. Thiele
A Robust Optimization Approach to Supply Chain Management