Access the full text.
Sign up today, get an introductory month for just $19.
Mohammad Mahdian, Y. Ye, Jiawei Zhang (2006)
Approximation Algorithms for Metric Facility Location ProblemsSIAM J. Comput., 36
Mohammad Mahdian, Y. Ye, Jiawei Zhang (2002)
Improved Approximation Algorithms for Metric Facility Location Problems
Stavros Kolliopoulos, N. Young (2001)
Tight approximation results for general covering integer programsProceedings 2001 IEEE International Conference on Cluster Computing
Naveen Garg, V. Vazirani, M. Yannakakis (1997)
Primal-dual approximation algorithms for integral flow and multicut in treesAlgorithmica, 18
M. Akgül (1984)
Topics in relaxation and ellipsoidal methods
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
Y. Ye, Jiawei Zhang (2004)
Approximation algorithms for facility location problems
Dan Suciu, V. Vianu (2006)
IntroductionJ. ACM, 53
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
Alexander ScHRJJVER, A. Mayne (1989)
Geometric Algorithms and Combinatorial OptimizationJournal of the Operational Research Society
D. Shmoys, É. Tardos, K. Aardal (1997)
Approximation algorithms for facility location problems (extended abstract)
(2005)
and M
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
Stavros Kolliopoulos, N. Young (2002)
Approximation algorithms for covering/packing integer programsJ. Comput. Syst. Sci., 71
(2005)
RECEIVED FEBRUARY
R. Ravi, Amitabh Sinha (2004)
Hedging Uncertainty: Approximation Algorithms for Stochastic Optimization ProblemsMathematical Programming, 108
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
V. Chvátal (1979)
A Greedy Heuristic for the Set-Covering ProblemMath. Oper. Res., 4
M. Dyer, L. Stougie (2006)
Computational complexity of stochastic programming problemsMathematical Programming, 106
A. Kleywegt, A. Shapiro, Tito Homem-de-Mello (2002)
The Sample Average Approximation Method for Stochastic Discrete OptimizationSIAM J. Optim., 12
J. Borwein, A. Lewis (2000)
Convex Analysis And Nonlinear Optimization
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
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)
Dimitris Bertsimas, Melvyn Sim (2003)
Robust discrete optimization and network flowsMathematical Programming, 98
A. Shapiro (2003)
Monte Carlo Sampling Methods, 10
Yu. Nesterov, J. Vial (2000)
Confidence level solutions for stochastic programmingAutom., 44
Stochastic optimization problems attempt to model uncertainty in the data by assuming that the input is specified by a probability distribution. We consider the well-studied paradigm of 2-stage models with recourse: first, given only distributional information about (some of) the data one commits on initial actions, and then once the actual data is realized (according to the distribution), further (recourse) actions can be taken. We show that for a broad class of 2-stage linear models with recourse, one can, for any ϵ > 0, in time polynomial in 1/ϵ and the size of the input, compute a solution of value within a factor (1+ϵ) of the optimum, in spite of the fact that exponentially many second-stage scenarios may occur. In conjunction with a suitable rounding scheme, this yields the first approximation algorithms for 2-stage stochastic integer optimization problems where the underlying random data is given by a “black box” and no restrictions are placed on the costs in the two stages. Our rounding approach for stochastic integer programs shows that an approximation algorithm for a deterministic analogue yields, with a small constant-factor loss, provably near-optimal solutions for the stochastic generalization. Among the range of applications, we consider are stochastic versions of the multicommodity flow, set cover, vertex cover, and facility location problems.
Journal of the ACM (JACM) – Association for Computing Machinery
Published: Nov 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 an introductory month for just $19.
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.