Approximation algorithms for (two) discrete stochastic optimization problems
| Speaker: | David Shmoys |
|---|---|
| Affiliation: | Cornell University |
| Room: | Mathematics & Computer Building (MC) 5158 |
Abstract:
One of the most active areas of research in the design of approximation algorithms is for discrete stochastic optimization problems, with a particular focus on 2-stage problems with recourse. Here, we are given a probability distribution over inputs, and the aim is to find a feasible solution that minimizes the expected cost of the solution found (with respect to the input distribution); an approximation algorithm finds a solution that is guaranteed to be nearly optimal. Techniques initially developed in the context of deterministic approximation, including rounding approaches, primal-dual algorithms, and randomization, have proved to be important in this context as well. We will focus on two specific examples, the a priori traveling salesman problem and a 2-stage stochastic single-machine scheduling problem, and for each, we will give an algorithm that is guaranteed to find a solution within a constant factor of optimal.
This is joint work with Mauro Sozio and Kunal Talwar.