Access the full text.
Sign up today, get DeepDyve free for 14 days.
Mohammad Mahdian, Y. Ye, Jiawei Zhang (2002)
Improved Approximation Algorithms for Metric Facility Location Problems
D. Shmoys, Chaitanya Swamy (2006)
An approximation scheme for stochastic linear programming and its application to stochastic integer programsJ. ACM, 53
R. Levi, Martin Pál, R. Roundy, D. Shmoys (2005)
Approximation Algorithms for Stochastic Inventory Control ModelsMath. Oper. Res., 32
M. Charikar, C. Chekuri, Martin Pál (2005)
Sampling Bounds for Stochastic Optimization
A. Shapiro, A. Nemirovski (2005)
On Complexity of Stochastic Programming Problems
S. Dye, L. Stougie, A. Tomasgard (1999)
The stochastic single node service provision problem, 9913
Anupam Gupta, Martin Pál, R. Ravi, Amitabh Sinha (2004)
Boosted sampling: approximation algorithms for stochastic optimization
J. Kleinberg, Y. Rabani, É. Tardos (1997)
Allocating bandwidth for bursty connectionsSIAM J. Comput., 30
E. Beale (1955)
ON MINIMIZING A CONVEX FUNCTION SUBJECT TO LINEAR INEQUALITIESJournal of the royal statistical society series b-methodological, 17
Chaitanya Swamy (2004)
Approximation Algorithms for Clustering Problems
A. Nemirovski, A. Shapiro (2006)
On complexity of Shmoys-Swamy class of two-stage linear stochastic programming problems
Mohammad Mahdian, D. Spielman (2004)
Facility location and the analysis of algorithms through factor-revealing programs
R. Levi, R. Roundy, D. Shmoys (2006)
Provably near-optimal sampling-based algorithms for Stochastic inventory control models
Anupam Gupta, Martin Pál, R. Ravi, Amitabh Sinha (2005)
What About Wednesday? Approximation Algorithms for Multistage Stochastic Optimization
B. Verweij, Shabbir Ahmed, A. Kleywegt, G. Nemhauser, A. Shapiro (2003)
The Sample Average Approximation Method Applied to Stochastic Routing Problems: A Computational StudyComputational Optimization and Applications, 24
R. Ravi, Amitabh Sinha (2004)
Hedging Uncertainty: Approximation Algorithms for Stochastic Optimization ProblemsMathematical Programming, 108
Kedar Dhamdhere, Vineet Goyal, R. Ravi, Mohit Singh (2005)
How to pay, come what may: approximation algorithms for demand-robust covering problems46th Annual IEEE Symposium on Foundations of Computer Science (FOCS'05)
G. Dantzig (2004)
Linear Programming Under UncertaintyManag. Sci., 50
K. Jain, V. Vazirani (2001)
Approximation algorithms for metric facility location and k-Median problems using the primal-dual schema and Lagrangian relaxationJ. ACM, 48
S. Dye, L. Stougie, A. Tomasgard (2003)
The stochastic single resource service‐provision problemNaval Research Logistics (NRL), 50
M. Dyer, L. Stougie (2006)
Computational complexity of stochastic programming problemsMathematical Programming, 106
Anupam Gupta, Martin Pál (2005)
Stochastic Steiner Trees Without a Root
A. Kleywegt, A. Shapiro, Tito Homem-de-Mello (2002)
The Sample Average Approximation Method for Stochastic Discrete OptimizationSIAM J. Optim., 12
Anupam Gupta, R. Ravi, Amitabh Sinha (2004)
An edge in time saves nine: LP rounding approximation algorithms for stochastic network design45th Annual IEEE Symposium on Foundations of Computer Science
(2003)
Editors, Stochastic Programming, volume 10 of Handbooks in Operations Research and Mgmt
R. Levi, R. Roundy, D. Shmoys (2007)
Provably Near-Optimal Sampling-Based Policies for Stochastic Inventory Control ModelsMath. Oper. Res., 32
Nicole Immorlica, David Karger, M. Minkoff, V. Mirrokni (2004)
On the costs and benefits of procrastination: approximation algorithms for stochastic combinatorial optimization problems
Jeff Linderoth, A. Shapiro, Stephen Wright (2006)
The empirical behavior of sampling methods for stochastic programmingAnnals of Operations Research, 142
(2006)
ACM SIGACT News
B. Dean, M. Goemans, J. Vondrák (2004)
Approximating the stochastic knapsack problem: the benefit of adaptivity45th Annual IEEE Symposium on Foundations of Computer Science
Chaitanya Swamy, D. Shmoys (2005)
The Sample Average Approximation Method for 2-stage Stochastic Optimization
D. Shmoys, Chaitanya Swamy (2004)
Stochastic optimization is (almost) as easy as deterministic optimization45th Annual IEEE Symposium on Foundations of Computer Science
Chaitanya Swamy, D. Shmoys (2005)
Sampling-based approximation algorithms for multi-stage stochastic optimization46th Annual IEEE Symposium on Foundations of Computer Science (FOCS'05)
Beale E. M. L.
173Journal of the Royal Statistical Society, Series B, 17
R. Möhring, Andreas Schulz, M. Uetz (1999)
Approximation in stochastic scheduling: the power of LP-based priority policiesJ. ACM, 46
M. Goemans, David Williamson (1992)
A general approximation technique for constrained forest problemsSIAM J. Comput., 24
R. Wets (1989)
Stochastic programmingOptimization
A. Shapiro (2003)
Monte Carlo Sampling Methods, 10
Kedar Dhamdhere, R. Ravi, Mohit Singh (2005)
On Two-Stage Stochastic Minimum Spanning Trees
Yu. Nesterov, J. Vial (2000)
Confidence level solutions for stochastic programmingAutom., 44
Uncertainty is a facet of many decision environments and might arise for various reasons, such as unpredictable information revealed in the future, or inherent fluctuations caused by noise. Stochastic optimization provides a means to handle uncertainty by modeling it by a probability distribution over possible realizations of the actual data, called scenarios. The field of stochastic optimization, or stochastic programming, has its roots in the work of Dantzig 4 and Beale 1 in the 1950s, and has since increasingly found application in a wide variety of areas, including transportation models, logistics, financial instruments, and network design. An important and widely-used model in stochastic programming is the 2-stage recourse model : first, given only distributional information about (some of) the data, one commits on initial ( first-stage ) actions. Then, once the actual data is realized according to the distribution, further recourse actions can be taken (in the second stage ) to augment the earlier solution and satisfy the revealed requirements. The aim is to choose the initial actions so as to minimize the expected total cost incurred. The recourse actions typically entail making decisions in rapid reaction to the observed scenario, and are therefore more costly than decisions made ahead of time. Thus there is a trade-off between committing initially, having only imprecise information while incurring a lower cost, and deferring decisions to the second-stage, when we know the input precisely but the costs are higher. Many applications can be modeled this way, and much of the textbook of Birge and Louveaux 2 is devoted to models and algorithms for this class of problems. A commonly cited example involves a setting where a company has to decide where to set up facilities to serve client demands. Typically the demand pattern is not known precisely at the outset, but one might be able to obtain, through simulation models or surveys, statistical information about the demands. This motivates the following 2-step decision process: in the first-stage, given only distributional information about the demands (and deterministic data for the facility opening costs), one must decide which facilities to open initially; once the client demands are realized according to this distribution, we can extend the solution by opening more facilities, incurring a recourse cost, and we have to assign the realized demands to open facilities. This is the 2-stage stochastic uncapacitated facility location problem. The recourse costs are usually higher than the original ones (because opening a facility later would involve deploying resources with a small lead time); these costs could be different for the different facilities, and could even depend on the realized scenario.
ACM SIGACT News – Association for Computing Machinery
Published: Mar 1, 2006
Read and print from thousands of top scholarly journals.
Already have an account? Log in
Bookmark this article. You can see your Bookmarks on your DeepDyve Library.
To save an article, log in first, or sign up for a DeepDyve account if you don’t already have one.
Copy and paste the desired citation format or use the link below to download a file formatted for EndNote
Access the full text.
Sign up today, get DeepDyve free for 14 days.
All DeepDyve websites use cookies to improve your online experience. They were placed on your computer when you launched this website. You can change your cookie settings through your browser.