Publication View

Hedging Uncertainty: Approximation Algorithms for Stochastic Optimization Problems (2005)

Abstract

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 Reviewed. http://deepblue.lib.umich.edu/bitstream/2027.42/45871/1/10107_2005_Article_673.pdf

Publication details

Download	, http://hdl.handle.net/2027.42/45871
Publisher	Springer-Verlag; Springer-Verlag Berlin Heidelberg
Contributors	Ross School of Business, , University of Michigan, , Ann Arbor, MI, 48109, USA, Tepper School of Business, , Carnegie Mellon University, , Pittsburgh, PA, 15213, USA, Ann Arbor
Repository	University of Michigan (United States)
Keywords	20C20, 20E28, Mathematical and Computational Physics, Numerical Analysis, Mathematics, Mathematics of Computing, Combinatorics, Calculus of Variations and Optimal Control, Optimization, Mathematical Methods in Physics, 20G40, Mathematics, Science
Language	English

Publications citing this publication (1)

Approximation in Stochastic integer programming (2005)