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 language | English (US) |
---|---|
Pages (from-to) | 86-98 |
Number of pages | 13 |
Journal | Lecture Notes in Computer Science |
Volume | 3624 |
DOIs | |
State | Published - 2005 |
Event | 8th 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 2005 → Aug 24 2005 |
ASJC Scopus subject areas
- Theoretical Computer Science
- General Computer Science