Approximation Algorithms for Discrete Stochastic Optimization Problems

We will survey recent work in the design of approximation algorithms for several discrete stochastic optimization problems, with a particular focus on 2-stage problems with recourse. In each of the problems we discuss, 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. Among the specific problems that we shall discuss are stochastic generalizations of the traditional deterministic facility location problem, a simple single-machine scheduling problem, and the traveling salesman problem.
These results build on techniques initially developed in the context of deterministic approximation, including rounding approaches, primal-dual algorithms, as well as a simple random sampling technique. Furthermore, although the focus of this stream of work was for discrete optimization problems, new insights for solving 2-stage stochastic linear programming problems were gained along the way.

Speaker Details

David Shmoys is a Professor of Operations Research and Information Engineering as well as of Computer Science at Cornell University. He obtained his Ph.D. in Computer Science from the University of California at Berkeley in 1984, and held postdoctoral positions at MSRI in Berkeley and Harvard University, and a faculty position at MIT before joining the Cornell faculty. Shmoys’s research has focused on the design and analysis of efficient algorithms for discrete optimization problems, and his work has highlighted the central role that linear programming plays in the design of approximation algorithms for NP-hard problems. He is a Fellow of the ACM, was an NSF Presidential Young Investigator, and has served on numerous editorial boards, including Mathematics of Operations Research, Operations Research, ORSA Journal on Computing, Mathematical Programming, and the SIAM Journals of both Computing and Discrete Mathematics.

Date:
Speakers:
David Shmoys
Affiliation:
Cornell University