{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,7]],"date-time":"2026-01-07T22:17:14Z","timestamp":1767824234027,"version":"3.49.0"},"reference-count":35,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2006,3,1]],"date-time":"2006-03-01T00:00:00Z","timestamp":1141171200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["SIGACT News"],"published-print":{"date-parts":[[2006,3]]},"abstract":"<jats:p>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<jats:italic>2-stage recourse model<\/jats:italic>: first, given only distributional information about (some of) the data, one commits on initial (<jats:italic>first-stage<\/jats:italic>) actions. Then, once the actual data is realized according to the distribution, further recourse actions can be taken (in the<jats:italic>second stage<\/jats:italic>) 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<jats:italic>2-stage stochastic uncapacitated facility location<\/jats:italic>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.<\/jats:p>","DOI":"10.1145\/1122480.1122493","type":"journal-article","created":{"date-parts":[[2006,5,8]],"date-time":"2006-05-08T22:51:53Z","timestamp":1147128713000},"page":"33-46","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":51,"title":["Approximation algorithms for 2-stage stochastic optimization problems"],"prefix":"10.1145","volume":"37","author":[{"given":"Chaitanya","family":"Swamy","sequence":"first","affiliation":[{"name":"Center for the Mathematics of Information, Caltech, Pasadena, CA"}]},{"given":"David B.","family":"Shmoys","sequence":"additional","affiliation":[{"name":"Cornell University, Ithaca, NY"}]}],"member":"320","published-online":{"date-parts":[[2006,3]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"crossref","first-page":"173","DOI":"10.1111\/j.2517-6161.1955.tb00191.x","article-title":"On minimizing a convex function subject to linear inequalities","volume":"17","author":"Beale E. M. L.","journal-title":"Journal of the Royal Statistical Society, Series B"},{"key":"e_1_2_1_2_1","unstructured":"J. R. Birge and F. V. Louveaux. Introduction to Stochastic Programming. Springer-Verlag NY 1997. J. R. Birge and F. V. Louveaux. Introduction to Stochastic Programming. Springer-Verlag NY 1997."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/11538462_22"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.1.3-4.197"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2004.15"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2005.42"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/11496915_24"},{"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":"eport 2002-05, Dept. of Mathematics and Computer Science","author":"Dyer M.","year":"2002"},{"key":"e_1_2_1_10_1","volume-title":"eport 2005-11, Dept. of Mathematics and Computer Science","author":"Dyer M.","year":"2005"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793242618"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/11523468_85"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007352.1007419"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/11538462_8"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2004.11"},{"key":"e_1_2_1_16_1","first-page":"684","volume-title":"Proceedings, 15th Annual ACM-SIAM Symposium on Discrete Algorithms","author":"Immorlica N.","year":"2004"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/375827.375845"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539797329142"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1137\/S1052623499363220"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/11496915_23"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/1132516.1132619"},{"key":"e_1_2_1_22_1","unstructured":"J. Linderoth A. Shapiro and R. K. Wright. The empirical behavior of sampling methods for stochastic programming. Annals of Operations Research to appear. J. Linderoth A. Shapiro and R. K. Wright. The empirical behavior of sampling methods for stochastic programming. Annals of Operations Research to appear."},{"key":"e_1_2_1_23_1","volume-title":"MIT","author":"Mahdian M.","year":"2004"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.5555\/646689.703120"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/331524.331530"},{"key":"e_1_2_1_26_1","volume-title":"CORE Discussion Papers, 2000","author":"Nesterov Y.","year":"2000"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-25960-2_8"},{"key":"e_1_2_1_28_1","doi-asserted-by":"crossref","unstructured":"A. Ruszczynski and A. Shapiro . Editors Stochastic Programming volume 10 of Handbooks in Operations Research and Mgmt . Sc. North-Holland Amsterdam 2003 . A. Ruszczynski and A. Shapiro. Editors Stochastic Programming volume 10 of Handbooks in Operations Research and Mgmt. Sc. North-Holland Amsterdam 2003.","DOI":"10.1016\/S0927-0507(03)10001-1"},{"key":"e_1_2_1_29_1","doi-asserted-by":"crossref","unstructured":"A. Shapiro . Monte Carlo sampling methods. In A. Ruszczynski and A. Shapiro editors Stochastic Programming volume 10 of Handbooks in Operations Research and Mgmt . Sc. North-Holland Amsterdam 2003 . A. Shapiro. Monte Carlo sampling methods. In A. Ruszczynski and A. Shapiro editors Stochastic Programming volume 10 of Handbooks in Operations Research and Mgmt. Sc. North-Holland Amsterdam 2003.","DOI":"10.1016\/S0927-0507(03)10006-0"},{"key":"e_1_2_1_30_1","unstructured":"A. Shapiro and A. Nemirovski. On complexity of stochastic programming problems. Published electronically in Optimization Online 2004. http:\/\/www.optimization-online.org\/DB_FILE\/2004\/10\/978.pdf. A. Shapiro and A. Nemirovski. On complexity of stochastic programming problems. Published electronically in Optimization Online 2004. http:\/\/www.optimization-online.org\/DB_FILE\/2004\/10\/978.pdf."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2004.62"},{"key":"e_1_2_1_32_1","volume-title":"Cornell University","author":"Swamy C.","year":"2004"},{"key":"e_1_2_1_33_1","unstructured":"C. Swamy and D. B. Shmoys. The sample average approximation method for 2-stage stochastic optimization. November 2004. http:\/\/ist.caltech.edu\/~cswamy\/papers\/SAAproof.pdf. C. Swamy and D. B. Shmoys. The sample average approximation method for 2-stage stochastic optimization. November 2004. http:\/\/ist.caltech.edu\/~cswamy\/papers\/SAAproof.pdf."},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2005.67"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1021814225969"}],"container-title":["ACM SIGACT News"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1122480.1122493","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1122480.1122493","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T16:08:37Z","timestamp":1750262917000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1122480.1122493"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006,3]]},"references-count":35,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2006,3]]}},"alternative-id":["10.1145\/1122480.1122493"],"URL":"https:\/\/doi.org\/10.1145\/1122480.1122493","relation":{},"ISSN":["0163-5700"],"issn-type":[{"value":"0163-5700","type":"print"}],"subject":[],"published":{"date-parts":[[2006,3]]},"assertion":[{"value":"2006-03-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}