Stochastic Depletion Problems

Vivek Farias
MIT Sloan School


Wednesday, November 28, 2007
4:30 - 5:30 PM
Terman Engineering Center, Room 453


Abstract:

We present a general class of dynamic stochastic optimization problems we refer to as `Stochastic Depletion Problems'. We isolate two simple properties, that if satisfied by a problem within this class, guarantee that a myopic policy is a 2-approximation to the optimal adaptive control policy for that problem. We check that these properties hold for an interesting family of problems within this class and thereby recover approximation guarantees for a number of challenging dynamic optimization problems. Some of these problems include Stochastic Broadcast Scheduling, Cost-per-Click AdWords Assignment and delay sensitive call-center scheduling. This is joint work with Carri Chan.

---

Operations Research Colloquia: http://or.stanford.edu/oras_seminars.html