|
Friday, April 4, 2008 |
|
|
|
|
Approximation algorithms for (two) discrete stochastic optimization problems |
|
|
One of the most active areas of research in the design of approximation
algorithms is for discrete {\it 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
{\it 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. |