{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T13:44:54Z","timestamp":1787319894240,"version":"build-2736575974"},"reference-count":40,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"1","funder":[{"DOI":"10.13039\/501100004281","name":"Polish National Science Centre","doi-asserted-by":"crossref","award":["2015\/18\/E\/ST6\/00456"],"award-info":[{"award-number":["2015\/18\/E\/ST6\/00456"]}],"id":[{"id":"10.13039\/501100004281","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/100004344","name":"Adobe Systems","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100004344","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100010664","name":"H2020 Future and Emerging Technologies","doi-asserted-by":"publisher","award":["FP6-021235-2"],"award-info":[{"award-number":["FP6-021235-2"]}],"id":[{"id":"10.13039\/100010664","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001870","name":"Fundacja na rzecz Nauki Polskiej","doi-asserted-by":"publisher","award":["Homing Plus\/2010-1\/3"],"award-info":[{"award-number":["Homing Plus\/2010-1\/3"]}],"id":[{"id":"10.13039\/501100001870","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004569","name":"Ministerstwo Nauki i Szkolnictwa Wy\u017cszego","doi-asserted-by":"publisher","award":["N N206 368839"],"award-info":[{"award-number":["N N206 368839"]}],"id":[{"id":"10.13039\/501100004569","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCR 0208005"],"award-info":[{"award-number":["CCR 0208005"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CNS 0426683"],"award-info":[{"award-number":["CNS 0426683"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CNS 0626636"],"award-info":[{"award-number":["CNS 0626636"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CNS 1010789"],"award-info":[{"award-number":["CNS 1010789"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1422569"],"award-info":[{"award-number":["CCF-1422569"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2018,1]]},"abstract":"<jats:p>We present improved approximation algorithms in stochastic optimization. We prove that the multistage stochastic versions of covering integer programs (such as set cover and vertex cover) admit essentially the same approximation algorithms as their standard (nonstochastic) counterparts; this improves upon work of Swamy and Shmoys which shows an approximability that depends multiplicatively on the number of stages. We also present approximation algorithms for facility location and some of its variants in the 2-stage recourse model, improving on previous approximation guarantees. We give a 2.2975-approximation algorithm in the standard polynomial-scenario model and an algorithm with an expected per-scenario 2.4957-approximation guarantee, which is applicable to the more general black-box distribution model.<\/jats:p>","DOI":"10.1137\/15m1043790","type":"journal-article","created":{"date-parts":[[2018,1,2]],"date-time":"2018-01-02T14:25:32Z","timestamp":1514903132000},"page":"44-63","source":"Crossref","is-referenced-by-count":6,"title":["Approximation Algorithms for Stochastic and Risk-Averse Optimization"],"prefix":"10.1137","volume":"32","author":[{"given":"Jaroslaw","family":"Byrka","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Aravind","family":"Srinivasan","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2018,1,2]]},"reference":[{"key":"atypb1","doi-asserted-by":"crossref","first-page":"173","DOI":"10.1111\/j.2517-6161.1955.tb00191.x","volume":"17","author":"E. M.","year":"1955","journal-title":"J. R. Stat. Soc. Ser. B"},{"key":"atypb2","unstructured":"J. R. Birge and F. V. Louveaux,\n                      Introduction to Stochastic Programming\n                      , Springer-Verlag, New York, 1997."},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.1137\/070708901"},{"key":"atypb4","doi-asserted-by":"crossref","unstructured":"M. Charikar, C. Chekuri, and M. Pa\u0301l,\n                      Sampling bounds for stochastic optimization\n                      , in Proceedings, 9th RANDOM, 2005, pp. 257-269.","DOI":"10.1007\/11538462_22"},{"key":"atypb5","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539703405754"},{"key":"atypb6","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.1.3-4.197"},{"key":"atypb7","doi-asserted-by":"publisher","DOI":"10.1287\/moor.1080.0330"},{"key":"atypb8","doi-asserted-by":"crossref","unstructured":"K. Dhamdhere, V. Goyal, R. Ravi, and M Singh,\n                      How to pay, come what may: Approximation algorithms for demand-robust covering problems\n                      , in Proceedings, 46th Annual IEEE Symposium on Foundations of Computer Science, 2005, pp. 367-378.","DOI":"10.1109\/SFCS.2005.42"},{"key":"atypb9","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-005-0597-0"},{"key":"atypb10","doi-asserted-by":"publisher","DOI":"10.1007\/BF01651330"},{"key":"atypb11","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1998.0993"},{"key":"atypb12","doi-asserted-by":"publisher","DOI":"10.1137\/080732250"},{"key":"atypb13","doi-asserted-by":"publisher","DOI":"10.1287\/moor.1060.0237"},{"key":"atypb14","unstructured":"N. Immorlica, D. Karger, M. Minkoff, and V. Mirrokni,\n                      On the costs and benefits of procrastination: Approximation algorithms for stochastic combinatorial optimization problems\n                      , in Proceedings, 15th Annual ACM-SIAM Symposium on Discrete Algorithms, 2004, pp. 684-693."},{"key":"atypb15","doi-asserted-by":"publisher","DOI":"10.1145\/950620.950621"},{"key":"atypb16","doi-asserted-by":"crossref","unstructured":"K. Jain, M. Mahdian, and A. Saberi,\n                      A new greedy approach for facility location problems\n                      , in Proceedings of the 34th Annual ACM Symposium on Theory of Computing, 2002, pp. 731-740.","DOI":"10.1145\/509907.510012"},{"key":"atypb17","doi-asserted-by":"publisher","DOI":"10.1137\/S1052623499363220"},{"key":"atypb18","doi-asserted-by":"crossref","unstructured":"S. Li,\n                      A\n                      1.488\n                      Approximation algorithm for the uncapacitated facility location problem\n                      , in Proceedings of the 38th ICALP, 2011, pp. 77-88.","DOI":"10.1007\/978-3-642-22012-8_5"},{"key":"atypb19","doi-asserted-by":"crossref","unstructured":"J.H. Lin and J. S. Vitter,\n                      Epsilon-approximations with minimum packing constraint violation (extended abstract)\n                      , in Proceedings, 24th Annual ACM Symposium on Theory of Computing, 1992, pp. 771-782.","DOI":"10.1145\/129712.129787"},{"key":"atypb20","doi-asserted-by":"publisher","DOI":"10.1007\/s10479-006-6169-8"},{"key":"atypb21","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539703435716"},{"key":"atypb22","doi-asserted-by":"publisher","DOI":"10.1145\/331524.331530"},{"key":"atypb23","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539792237462"},{"key":"atypb24","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793250767"},{"key":"atypb25","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579324"},{"key":"atypb26","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-005-0673-5"},{"key":"atypb27","doi-asserted-by":"crossref","unstructured":"A. Ruszczynski and A. Shapiro, eds., Stochastic Programming, Vol. 10 of Handbooks in Operations Research and Management Science, North-Holland, Amsterdam, 2003.","DOI":"10.1016\/S0927-0507(03)10001-1"},{"key":"atypb28","doi-asserted-by":"crossref","unstructured":"A. Shapiro,\n                      Monte Carlo sampling methods\n                      , In A. Ruszczynski and A. Shapiro, eds., Stochastic Programming, Vol. 10 of Handbooks in Operations Research and Management Science, North-Holland, Amsterdam, 2003.","DOI":"10.1016\/S0927-0507(03)10006-0"},{"key":"atypb29","unstructured":"A. Shapiro and A. Nemirovski,\n                      On complexity of stochastic programming problems\n                      , published electronically in Optimization Online, 2004,http:\/\/www.optimization- online.org\/DB_FILE\/2004\/10\/978.pdf."},{"key":"atypb30","doi-asserted-by":"publisher","DOI":"10.1145\/1217856.1217860"},{"key":"atypb31","doi-asserted-by":"crossref","unstructured":"D. B. Shmoys, E\u0301. Tardos, and K. I. Aardal,\n                      Approximation algorithms for facility location problems\n                      , in Proceedings of the 29th Annual ACM Symposium on Theory of Computing, pp. 265-274.","DOI":"10.1145\/258533.258600"},{"key":"atypb32","doi-asserted-by":"publisher","DOI":"10.1287\/moor.1090.0390"},{"key":"atypb33","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539796314240"},{"key":"atypb34","unstructured":"A. Srinivasan,\n                      Approximation algorithms for stochastic and risk-averse optimization\n                      , in Proceedings, 18th SODA, 2007, pp. 1305-1313."},{"key":"atypb35","doi-asserted-by":"crossref","unstructured":"M. Sviridenko,\n                      An improved approximation algorithm for the metric uncapacitated facility location problem\n                      , in Proceedings of the 9th International Conference on Integer Programming and Combinatorial Optimization, 2002, pp. 240-257.","DOI":"10.1007\/3-540-47867-1_18"},{"key":"atypb36","unstructured":"C. Swamy,\n                      Approximation Algorithms for Clustering Problems\n                      , Ph.D. thesis, Cornell University, Ithaca, NY, 2004."},{"key":"atypb37","doi-asserted-by":"crossref","unstructured":"C. Swamy,\n                      Risk-averse stochastic optimization: Probabilistically-constrained models and algorithms for black-box distributions\n                      , in Proceedings, 22nd SODA, 2011, pp. 1627-1646.","DOI":"10.1137\/1.9781611973082.126"},{"key":"atypb38","doi-asserted-by":"publisher","DOI":"10.1137\/100789269"},{"key":"atypb39","doi-asserted-by":"publisher","DOI":"10.1145\/1122480.1122493"},{"key":"atypb40","doi-asserted-by":"publisher","DOI":"10.1023\/A:1021814225969"}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/15M1043790","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T12:53:37Z","timestamp":1787316817000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/15M1043790"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,1]]},"references-count":40,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2018,1]]}},"alternative-id":["10.1137\/15M1043790"],"URL":"https:\/\/doi.org\/10.1137\/15m1043790","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,1]]}}}