License
when quoting this document, please refer to the following
URN: urn:nbn:de:0030-drops-12906
URL: http://drops.dagstuhl.de/opus/volltexte/2007/1290/

Swamy, Chaitanya ; Shmoys, David

Sampling-based Approximation Algorithms for Multi-stage Stochastic Optimization

pdf-format:
Dokument 1.pdf (281 KB)


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 data. We consider a broad class of these problems, called {it multi-stage stochastic programming problems with recourse}, where the uncertainty evolves through a series of stages and one take decisions in each stage in response to the new information learned. These problems are often computationally quite difficult with even very specialized (sub)problems being $#P$-complete. We obtain the first fully polynomial randomized approximation scheme (FPRAS) for a broad class of multi-stage stochastic linear programming problems with any constant number of stages, without placing any restrictions on the underlying probability distribution or on the cost structure of the input. For any fixed $k$, for a rich class of $k$-stage stochastic linear programs (LPs), we show that, for any probability distribution, for any $epsilon>0$, one can compute, with high probability, a solution with expected cost at most $(1+e)$ times the optimal expected cost, in time polynomial in the input size, $frac{1}{epsilon}$, and a parameter $lambda$ that is an upper bound on the cost-inflation over successive stages. Moreover, the algorithm analyzed is a simple and intuitive algorithm that is often used in practice, the {it sample average approximation} (SAA) method. In this method, one draws certain samples from the underlying distribution, constructs an approximate distribution from these samples, and solves the stochastic problem given by this approximate distribution. This is the first result establishing that the SAA method yields near-optimal solutions for (a class of) multi-stage programs with a polynomial number of samples. As a corollary of this FPRAS, by adapting a generic rounding technique of Shmoys and Swamy, we also obtain the first approximation algorithms for the analogous class of multi-stage stochastic integer programs, which includes the multi-stage versions of the set cover, vertex cover, multicut on trees, facility location, and multicommodity flow problems.

BibTeX - Entry

@InProceedings{swamy_et_al:DSP:2007:1290,
  author =	{Chaitanya Swamy and David Shmoys},
  title =	{Sampling-based Approximation Algorithms for Multi-stage Stochastic Optimization},
  booktitle =	{Probabilistic Methods in the Design and Analysis of Algorithms},
  year =	{2007},
  editor =	{Martin Dietzfelbinger and Shang-Hua Teng and Eli Upfal and Berthold V{\"o}cking },
  number =	{07391},
  series =	{Dagstuhl Seminar Proceedings},
  ISSN =	{1862-4405},
  publisher =	{Internationales Begegnungs- und Forschungszentrum f{\"u}r Informatik (IBFI), Schloss Dagstuhl, Germany},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2007/1290},
  annote =	{Keywords: Stochastic optimization, approximation algorithms, randomized algorithms, linear programming}
}

Keywords: Stochastic optimization, approximation algorithms, randomized algorithms, linear programming
Seminar: 07391 - Probabilistic Methods in the Design and Analysis of Algorithms
Issue date: 2007
Date of publication: 18.12.2007


DROPS-Home | Fulltext Search | Imprint Published by LZI