What about wednesday? Approximation algorithms for multistage stochastic optimization

Anupam Gupta, Martin Pál, Ramamoorthi Ravi, Amitabh Sinha

Research output: Contribution to journalConference articlepeer-review

Abstract

We study the problem of multi-stage stochastic optimization with recourse, and provide approximation algorithms using cost-sharing functions for such problems. Our algorithms use and extend the Boosted Sampling framework of [6]. We also show how the framework can be adapted to give approximation algorithms even when the inflation parameters are correlated with the scenarios.

Original languageEnglish (US)
Pages (from-to)86-98
Number of pages13
JournalLecture Notes in Computer Science
Volume3624
DOIs
StatePublished - 2005
Event8th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2005 and 9th International Workshop on Randomization and Computation, RANDOM 2005 - Berkeley, CA, United States
Duration: Aug 22 2005Aug 24 2005

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science

Fingerprint

Dive into the research topics of 'What about wednesday? Approximation algorithms for multistage stochastic optimization'. Together they form a unique fingerprint.

Cite this