Approximation Algorithms for Discrete Stochastic Optimization Problems
<--
Return to the list
Date: 12-04-2007
Start Time:
1:00pm
End Time: 2:00pm
Speaker: David Shmoys, Cornell University
Location: Mudd 303
ABSTRACT
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. These results have
built 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.
BIO
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.
