{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,10]],"date-time":"2025-11-10T20:50:30Z","timestamp":1762807830889},"reference-count":30,"publisher":"Association for Computing Machinery (ACM)","issue":"6","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2006,11]]},"abstract":"<jats:p>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 \u03f5 &gt; 0, in time polynomial in 1\/\u03f5 and the size of the input, compute a solution of value within a factor (1+\u03f5) 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 \u201cblack box\u201d 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.<\/jats:p>","DOI":"10.1145\/1217856.1217860","type":"journal-article","created":{"date-parts":[[2007,4,5]],"date-time":"2007-04-05T19:20:08Z","timestamp":1175800808000},"page":"978-1012","update-policy":"http:\/\/dx.doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":73,"title":["An approximation scheme for stochastic linear programming and its application to stochastic integer programs"],"prefix":"10.1145","volume":"53","author":[{"given":"David B.","family":"Shmoys","sequence":"first","affiliation":[{"name":"Cornell University, Ithaca, New York"}]},{"given":"Chaitanya","family":"Swamy","sequence":"additional","affiliation":[{"name":"University of Waterloo, Waterloo, Ontario, Canada"}]}],"member":"320","published-online":{"date-parts":[[2006,11]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.2517-6161.1955.tb00191.x"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-003-0396-4"},{"key":"e_1_2_1_3_1","unstructured":"Birge J. R. and Louveaux F. V. 1997. Introduction to Stochastic Programming. Springer-Verlag New York.  Birge J. R. and Louveaux F. V. 1997. Introduction to Stochastic Programming. Springer-Verlag New York."},{"key":"e_1_2_1_4_1","doi-asserted-by":"crossref","unstructured":"Borwein J. and Lewis A. S. 2000. Convex Analysis and Nonlinear Optimization. Springer-Verlag New York.  Borwein J. and Lewis A. S. 2000. Convex Analysis and Nonlinear Optimization. Springer-Verlag New York.","DOI":"10.1007\/978-1-4757-9859-3"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/11538462_22"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.4.3.233"},{"key":"e_1_2_1_7_1","first-page":"197","article-title":"Linear programming under uncertainty. Manage","volume":"1","author":"Dantzig G. B.","year":"1955","journal-title":"Sci."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1002\/nav.10092"},{"key":"e_1_2_1_9_1","volume-title":"Tech. Rep. SPOR-Report 2002-05, Dept. of Mathematics and Computer Science","author":"Dyer M.","year":"2002"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-005-0597-0"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02523685"},{"key":"e_1_2_1_12_1","doi-asserted-by":"crossref","unstructured":"Gr\u00f6tschel M. Lov\u00e1sz L. and Schrijver A. 1988. Geometric Algorithms and Combinatorial Optimization. Springer-Verlag New York.  Gr\u00f6tschel M. Lov\u00e1sz L. and Schrijver A. 1988. Geometric Algorithms and Combinatorial Optimization. Springer-Verlag New York.","DOI":"10.1007\/978-3-642-97881-4"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007352.1007419"},{"key":"e_1_2_1_14_1","volume-title":"Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms. 684--693","author":"Immorlica N."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1137\/S1052623499363220"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2005.05.002"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10479-006-6169-8"},{"key":"e_1_2_1_18_1","unstructured":"Mahdian M. 2004. Facility location and the analysis of algorithms through factor-revealing programs. Ph.D. dissertation MIT Cambridge MA.   Mahdian M. 2004. Facility location and the analysis of algorithms through factor-revealing programs. Ph.D. dissertation MIT Cambridge MA."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539703435716"},{"key":"e_1_2_1_20_1","unstructured":"Nemirovski A. and Shapiro A. 2006. On complexity of Shmoys-Swamy class of two-stage linear stochastic programming problems. Optim. Online. http:\/\/www.optimization-online.org\/DB_FILE\/2006\/07\/1434.pdf.  Nemirovski A. and Shapiro A. 2006. On complexity of Shmoys-Swamy class of two-stage linear stochastic programming problems. Optim. Online. http:\/\/www.optimization-online.org\/DB_FILE\/2006\/07\/1434.pdf."},{"key":"e_1_2_1_21_1","unstructured":"Nesterov Y. and Vial J.-P. 2000. Confidence level solutions for stochastic programming. Tech. Rep. CORE Discussion Papers. http:\/\/www.core.ucl.ac.be\/services\/psfiles\/dp00\/dp2000-13.pdf.  Nesterov Y. and Vial J.-P. 2000. Confidence level solutions for stochastic programming. Tech. Rep. CORE Discussion Papers. http:\/\/www.core.ucl.ac.be\/services\/psfiles\/dp00\/dp2000-13.pdf."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-005-0673-5"},{"key":"e_1_2_1_23_1","volume-title":"Eds. Handbooks in Operations Research and Management Science","volume":"10","author":"Shapiro A.","year":"2003"},{"key":"e_1_2_1_24_1","volume-title":"Eds. Applied Optimization","volume":"99","author":"Shapiro A.","year":"2004"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2004.62"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/258533.258600"},{"key":"e_1_2_1_27_1","unstructured":"Swamy C. 2004. Approximation algorithms for clustering problems. Ph.D. dissertation Cornell University Ithaca New York. http:\/\/www.math.uwaterloo.ca\/~cswamy\/theses\/master.pdf.   Swamy C. 2004. Approximation algorithms for clustering problems. Ph.D. dissertation Cornell University Ithaca New York. http:\/\/www.math.uwaterloo.ca\/~cswamy\/theses\/master.pdf."},{"key":"e_1_2_1_28_1","unstructured":"Swamy C. and Shmoys D. B. 2004. The sample average approximation method for 2-stage stochastic optimization. http:\/\/www.math.uwaterloo.ca\/~cswamy\/papers\/SAAproof.pdf.  Swamy C. and Shmoys D. B. 2004. The sample average approximation method for 2-stage stochastic optimization. http:\/\/www.math.uwaterloo.ca\/~cswamy\/papers\/SAAproof.pdf."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2005.67"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1021814225969"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1217856.1217860","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T21:32:34Z","timestamp":1672263154000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1217856.1217860"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006,11]]},"references-count":30,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2006,11]]}},"alternative-id":["10.1145\/1217856.1217860"],"URL":"https:\/\/doi.org\/10.1145\/1217856.1217860","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2006,11]]},"assertion":[{"value":"2006-11-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}