CaltechAUTHORS
  A Caltech Library Service

Sampling-based approximation algorithms for multi-stage stochastic optimization

Swamy, Chaitanya and Shmoys, David B. (2005) Sampling-based approximation algorithms for multi-stage stochastic optimization. In: 46th Annual IEEE Symposium on Foundations of Computer Science. IEEE International Conference on Robotics and Automation. IEEE , Los Alamitos, CA, pp. 357-366. ISBN 0-7695-2468-0 http://resolver.caltech.edu/CaltechAUTHORS:20110825-111116375

Full text is not posted in this repository. Consult Related URLs below.

Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechAUTHORS:20110825-111116375

Abstract

Stochastic optimization problems provide a means to model uncertainty in the input data where the uncertainty is modeled by a probability distribution over the possible realizations of the actual data. We consider a broad class of these problems in which the realized input is revealed through a series of stages, and hence are called multi-stage stochastic programming problems. Our main result is to give the first fully polynomial approximation scheme for a broad class of multi-stage stochastic linear programming problems with any constant number of stages. The algorithm analyzed, known as the sample average approximation (SAA) method, is quite simple, and is the one most commonly used in practice. The algorithm accesses the input by means of a "black box" that can generate, given a series of outcomes for the initial stages, a sample of the input according to the conditional probability distribution (given those outcomes). We use this to obtain the first polynomial-time approximation algorithms for a variety of k-stage generalizations of basic combinatorial optimization problems.


Item Type:Book Section
Related URLs:
URLURL TypeDescription
http://dx.doi.org/10.1109/SFCS.2005.67 DOIUNSPECIFIED
http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=1530728PublisherUNSPECIFIED
Additional Information:© 2005 IEEE. Issue Date: 23-25 Oct. 2005. Date of Current Version: 14 November 2005.
Other Numbering System:
Other Numbering System NameOther Numbering System ID
INSPEC Accession Number8814627
Record Number:CaltechAUTHORS:20110825-111116375
Persistent URL:http://resolver.caltech.edu/CaltechAUTHORS:20110825-111116375
Official Citation:Swamy, C.; Shmoys, D.B.; , "Sampling-based approximation algorithms for multi-stage stochastic optimization," Foundations of Computer Science, 2005. FOCS 2005. 46th Annual IEEE Symposium on , vol., no., pp. 357- 366, 23-25 Oct. 2005 doi: 10.1109/SFCS.2005.67 URL: http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=1530728&isnumber=32664
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:25092
Collection:CaltechAUTHORS
Deposited By: Tony Diaz
Deposited On:25 Aug 2011 18:46
Last Modified:25 Aug 2011 18:46

Repository Staff Only: item control page