演讲人： David Shmoys Cornell University
时间： 2006-03-20 14:00-2006-03-20 15:00
地点：FIT Building, Tsinghua University
内容：

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; they have been studied since the 50's, and have become an important paradigm in a wide range of application areas, including transportation models, logistics, financial instruments, and network design. Particular attention has been paid to 2-stage models with recourse: 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 pose significant computational obstacles, both from a practical perspective, as well as from the point of view of complexity theory.
Little attention had been paid to the question of designing approximation algorithms for discrete stochastic optimization problems, and we will present algorithms with a constant performance guarantee for a large class of 2-stage discrete stochastic optimization problems with recourse in which the underlying random data is given by a "black box". We consider a number of applications, including stochastic versions of the vertex cover problem, the facility location problem, and the multicommodity flow problem. One of the tools derived in this work is a randomized fully polynomial approximation scheme for the analogous class of 2-stage stochastic linear programming problems, which is a result of interest in its own right.
 

个人简介: