{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,1,12]],"date-time":"2025-01-12T06:10:03Z","timestamp":1736662203910,"version":"3.32.0"},"publisher-location":"Berlin, Heidelberg","reference-count":29,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540499947"},{"type":"electronic","value":"9783540499954"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2006]]},"DOI":"10.1007\/11944836_3","type":"book-chapter","created":{"date-parts":[[2006,11,28]],"date-time":"2006-11-28T04:48:02Z","timestamp":1164689282000},"page":"5-19","source":"Crossref","is-referenced-by-count":5,"title":["Approximation Algorithms for 2-Stage Stochastic Optimization Problems"],"prefix":"10.1007","author":[{"given":"Chaitanya","family":"Swamy","sequence":"first","affiliation":[]},{"given":"David B.","family":"Shmoys","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"3_CR1","doi-asserted-by":"crossref","first-page":"173","DOI":"10.1111\/j.2517-6161.1955.tb00191.x","volume":"17","author":"E.M.L. Beale","year":"1955","unstructured":"Beale, E.M.L.: On minimizing a convex function subject to linear inequalities. J. Royal Stat. Soc., Series B.\u00a017, 173\u2013184; discussion 194\u2013203 (1955)","journal-title":"J. Royal Stat. Soc., Series B."},{"key":"3_CR2","volume-title":"Introduction to Stochastic Programming","author":"J.R. Birge","year":"1997","unstructured":"Birge, J.R., Louveaux, F.V.: Introduction to Stochastic Programming. Springer, New York (1997)"},{"key":"3_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"257","DOI":"10.1007\/11538462_22","volume-title":"Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques","author":"M. Charikar","year":"2005","unstructured":"Charikar, M., Chekuri, C., P\u00e1l, M.: Sampling bounds for stochastic optimization. In: Chekuri, C., Jansen, K., Rolim, J.D.P., Trevisan, L. (eds.) APPROX 2005 and RANDOM 2005. LNCS, vol.\u00a03624, pp. 257\u2013269. Springer, Heidelberg (2005)"},{"key":"3_CR4","doi-asserted-by":"publisher","first-page":"197","DOI":"10.1287\/mnsc.1.3-4.197","volume":"1","author":"G.B. Dantzig","year":"1955","unstructured":"Dantzig, G.B.: Linear programming under uncertainty. Management Sci.\u00a01, 197\u2013206 (1955)","journal-title":"Management Sci."},{"key":"3_CR5","doi-asserted-by":"crossref","unstructured":"Dean, B., Goemans, M.X., Vondrak, J.: Approximating the stochastic knapsack problem: the benefit of adaptivity. In: Proc. 45th Annual IEEE Symposium on Foundations of Computer Science, pp. 208\u2013217 (2004)","DOI":"10.1109\/FOCS.2004.15"},{"key":"3_CR6","doi-asserted-by":"publisher","first-page":"869","DOI":"10.1002\/nav.10092","volume":"50","author":"S. Dye","year":"2003","unstructured":"Dye, S., Stougie, L., Tomasgard, A.: The stochastic single resource service-provision problem. Naval Res. Logistics\u00a050, 869\u2013887 (2003); Also appeared as, The stochastic single node service provision problem. COSOR-Memorandum 99-13, Dept. Math. & Comp. Sc., Eindhoven Tech. Univ., Eindhoven (1999)","journal-title":"Naval Res. Logistics"},{"key":"3_CR7","unstructured":"Dyer, M., Kannan, R., Stougie, L.: A simple randomised algorithm for convex optimisation. SPOR-Report 2002-05, Dept. Math. & Comp. Sc., Eindhoven Tech. Univ., Eindhoven (2002)"},{"key":"3_CR8","unstructured":"Dyer, M., Stougie, L.: Computational complexity of stochastic programming problems. SPOR-Report 2005-11, Dept. Math. & Comp. Sc., Eindhoven Tech. Univ., Eindhoven (2005)"},{"key":"3_CR9","doi-asserted-by":"publisher","first-page":"296","DOI":"10.1137\/S0097539793242618","volume":"24","author":"M.X. Goemans","year":"1995","unstructured":"Goemans, M.X., Williamson, D.P.: A general approximation technique for constrained forest problems. SIAM J. Comput.\u00a024, 296\u2013317 (1995)","journal-title":"SIAM J. Comput."},{"key":"3_CR10","doi-asserted-by":"crossref","unstructured":"Gupta, A., P\u00e1l, M., Ravi, R., Sinha, A.: Boosted sampling: approximation algorithms for stochastic optimization. In: Proc. 36th ACM STOC, pp. 417\u2013426 (2004)","DOI":"10.1145\/1007352.1007419"},{"key":"3_CR11","unstructured":"Immorlica, N., Karger, D., Minkoff, M., Mirrokni, V.: On the costs and benefits of procrastination: approximation algorithms for stochastic combinatorial optimization problems. In: Proc. 15th SODA, pp. 684\u2013693 (2004)"},{"key":"3_CR12","doi-asserted-by":"publisher","first-page":"274","DOI":"10.1145\/375827.375845","volume":"48","author":"K. Jain","year":"2001","unstructured":"Jain, K., Vazirani, V.V.: Approximation algorithms for metric facility location and k-median problems using the primal-dual schema and Lagrangian relaxation. J. ACM\u00a048, 274\u2013296 (2001)","journal-title":"J. ACM"},{"key":"3_CR13","doi-asserted-by":"publisher","first-page":"191","DOI":"10.1137\/S0097539797329142","volume":"30","author":"J. Kleinberg","year":"2000","unstructured":"Kleinberg, J., Rabani, Y., Tardos, \u00c9.: Allocating bandwidth for bursty connections. SIAM J. Comput.\u00a030, 191\u2013217 (2000)","journal-title":"SIAM J. Comput."},{"key":"3_CR14","doi-asserted-by":"publisher","first-page":"479","DOI":"10.1137\/S1052623499363220","volume":"12","author":"A.J. Kleywegt","year":"2001","unstructured":"Kleywegt, A.J., Shapiro, A., Homem-De-Mello, T.: The sample average approximation method for stochastic discrete optimization. SIAM J. Optimization\u00a012, 479\u2013502 (2001)","journal-title":"SIAM J. Optimization"},{"key":"3_CR15","doi-asserted-by":"crossref","unstructured":"Linderoth, J., Shapiro, A., Wright, S.: The empirical behavior of sampling methods for stochastic programming. Annals Oper. Res. (to appear)","DOI":"10.1007\/s10479-006-6169-8"},{"key":"3_CR16","unstructured":"Mahdian, M.: Facility Location and the Analysis of Algorithms through Factor-revealing Programs. Ph.D. thesis, MIT, Cambridge, MA (2004)"},{"key":"3_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"229","DOI":"10.1007\/3-540-45753-4_20","volume-title":"Approximation Algorithms for Combinatorial Optimization","author":"M. Mahdian","year":"2002","unstructured":"Mahdian, M., Ye, Y., Zhang, J.: Improved approximation algorithms for metric facility location problems. In: Jansen, K., Leonardi, S., Vazirani, V.V. (eds.) APPROX 2002. LNCS, vol.\u00a02462, p. 229. Springer, Heidelberg (2002)"},{"key":"3_CR18","doi-asserted-by":"publisher","first-page":"924","DOI":"10.1145\/331524.331530","volume":"46","author":"R. M\u00f6hring","year":"1999","unstructured":"M\u00f6hring, R., Schulz, A., Uetz, M.: Approximation in stochastic scheduling: the power of LP based priority policies. JACM\u00a046, 924\u2013942 (1999)","journal-title":"JACM"},{"key":"3_CR19","unstructured":"Nemirovski, A., Shapiro, A.: On complexity of Shmoys\u2013Swamy class of two-stage linear stochastic programming problems (2006) Optimization Online, http:\/\/www.optimization-online.org\/DB_FILE\/2006\/07\/1434.pdf"},{"key":"3_CR20","unstructured":"Nesterov, Y., Vial, J.-P.: Confidence level solutions for stochastic programming. CORE Discussion Papers (2000), http:\/\/www.core.ucl.ac.be\/services\/psfiles\/dp00\/dp2000-13.pdf"},{"key":"3_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"101","DOI":"10.1007\/978-3-540-25960-2_8","volume-title":"Integer Programming and Combinatorial Optimization","author":"R. Ravi","year":"2004","unstructured":"Ravi, R., Sinha, A.: Hedging uncertainty: Approximation algorithms for stochastic optimization problems. In: Bienstock, D., Nemhauser, G.L. (eds.) IPCO 2004. LNCS, vol.\u00a03064, pp. 101\u2013115. Springer, Heidelberg (2004)"},{"key":"3_CR22","series-title":"Handbooks in Oper. Res. & Mgmt. Sc.","volume-title":"Stochastic Programming","year":"2003","unstructured":"Ruszczynski, A., Shapiro, A. (eds.): Stochastic Programming. Handbooks in Oper. Res. & Mgmt. Sc., vol.\u00a010. North-Holland, Amsterdam (2003)"},{"key":"3_CR23","series-title":"Handbooks in Oper. Res. & Mgmt. Sc.","doi-asserted-by":"publisher","DOI":"10.1016\/S0927-0507(03)10006-0","volume-title":"Stochastic Programming","author":"A. Shapiro","year":"2003","unstructured":"Shapiro, A.: Monte Carlo sampling methods. In: Ruszczynski, A., Shapiro, A. (eds.) Stochastic Programming. Handbooks in Oper. Res. & Mgmt. Sc., vol.\u00a010, North-Holland, Amsterdam (2003)"},{"key":"3_CR24","unstructured":"Shapiro, A., Nemirovski, A.: On complexity of stochastic programming problems (2004), Optimization Online, http:\/\/www.optimization-online.org\/DB_FILE\/2004\/10\/978.pdf"},{"key":"#cr-split#-3_CR25.1","doi-asserted-by":"crossref","unstructured":"Shmoys, D.B., Swamy, C.: An approximation scheme for stochastic linear programming and its application to stochastic integer programs. J. ACM (to appear);","DOI":"10.1145\/1217856.1217860"},{"key":"#cr-split#-3_CR25.2","unstructured":"Preliminary version appeared as Stochastic optimization is (almost) as easy as deterministic optimization. In: Proc. 45th Annual IEEE FOCS, pp. 228???237 (2004)"},{"key":"3_CR26","unstructured":"Swamy, C.: Approximation Algorithms for Clustering Problems. Ph.D. thesis, Cornell Univ., Ithaca, NY (May 2004), http:\/\/www.math.uwaterloo.ca\/cswamy\/theses\/master.pdf"},{"key":"3_CR27","unstructured":"Swamy, C., Shmoys, D.B.: The sample average approximation method for 2-stage stochastic optimization (November 2004), http:\/\/www.math.uwaterloo.ca\/cswamy\/papers\/SAAproof.pdf"},{"key":"3_CR28","doi-asserted-by":"publisher","first-page":"289","DOI":"10.1023\/A:1021814225969","volume":"24","author":"B. Verweij","year":"2003","unstructured":"Verweij, B., Ahmed, S., Kleywegt, A.J., Nemhauser, G.L., Shapiro, A.: The sample average approximation method applied to stochastic routing problems: a computational study. Comp. Opt. Appl.\u00a024, 289\u2013333 (2003)","journal-title":"Comp. Opt. Appl."}],"container-title":["Lecture Notes in Computer Science","FSTTCS 2006: Foundations of Software Technology and Theoretical Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11944836_3.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,12]],"date-time":"2025-01-12T05:02:58Z","timestamp":1736658178000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11944836_3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006]]},"ISBN":["9783540499947","9783540499954"],"references-count":29,"URL":"https:\/\/doi.org\/10.1007\/11944836_3","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2006]]}}}