Seminario Interdipartimentale di Algoritmica
 

Monday, November 8, 2004, 12:00 noon
Algorithms for Stochastic Optimization Problems
Chaitanya Swamy
California Institute of Technology

DIS - Department of Computer and System Sciences
C3 Room, second floor

Abstract:

Stochastic optimization problems attempt to model uncertainty in the data by assuming that (part of) the input is specified in terms of a probability distribution, rather than by deterministic data given in advance. We consider the well-syudied paradigm of 2-stage models with recourse, where one takes decisions in two steps: first, given only distributional information about (some of) the data one commits on initial actions, and then once the actual data is realized (according to the distribution), further (recourse) actions can be taken. These problems are often computationally quite difficult, both from a practical perspective, as well as from the point of view of complexity theory. We give the first approximation algorithms for 2-stage stochastic optimization problems with recourse for which the underlying random data is given by a "black box" and no restrictions are placed on the costs of the two stages, based on an approximation scheme for a linear programming (LP) relaxation of the problem. A significant difficulty encountered, is that the LP relaxation of the stochastic problem may have an exponential number of variables and constraints, and might not be solvable in polynomial time; in fact, even evaluating the objective function may be #P-hard. In this talk, I will describe the algorithm used to solve these exponential size LPs, and show how this can be applied to design approximation algorithms for some applications such as the stochastic versions of the set cover, vertex cover and facility location problems.

This is joint work with David Shmoys