Hedging Uncertainty: Approximation Algorithms for Stochastic Optimization Problems

We study two-stage, finite-scenario stochastic versions of several combinatorial optimization problems, and provide nearly tight approximation algorithms for them. Our problems range from the graph-theoretic (shortest path, vertex cover, facility location) to set-theoretic (set cover, bin packing), and contain representatives with different approximation ratios.Peer Reviewedhttp://deepblue.lib.umich.edu/bitstream/2027.42/45871/1/10107_2005_Article_673.pd