{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:27:51Z","timestamp":1787340471443,"version":"build-2736575974"},"reference-count":48,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"5","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2011,1]]},"abstract":"<jats:p>We consider two- and multistage versions of stochastic combinatorial optimization problems with recourse: in this framework, the instance for the combinatorial optimization problem is drawn from a known probability distribution $\\pi$ and is only revealed to the algorithm over two (or multiple) stages. At each stage, on receiving some more information about the instance, the algorithm is allowed to build some partial solution. Since the costs of elements increase with each passing stage, there is a natural tension between waiting for later stages, to gain more information about the instance, and purchasing elements in earlier stages, to take advantages of lower costs. We provide approximation algorithms for stochastic combinatorial optimization problems (such as the Steiner tree problem, the Steiner network problem, and the vertex cover problem) by means of a simple sampling-based algorithm. In every stage, our algorithm samples the probability distribution of the requirements and constructs a partial solution to serve the resulting sample. We show that if one can construct cost-sharing functions associated with the algorithms used to construct these partial solutions, then this strategy results in provable approximation guarantees for the overall stochastic optimization problem. We also extend this approach to provide an approximation algorithm for the stochastic version of the uncapacitated facility location problem, a problem that does not fit into the simpler framework of our main model.<\/jats:p>","DOI":"10.1137\/080732250","type":"journal-article","created":{"date-parts":[[2011,9,28]],"date-time":"2011-09-28T00:26:20Z","timestamp":1317169580000},"page":"1361-1401","source":"Crossref","is-referenced-by-count":17,"title":["Sampling and Cost-Sharing: Approximation Algorithms for Stochastic Optimization Problems"],"prefix":"10.1137","volume":"40","author":[{"given":"Anupam","family":"Gupta","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Martin","family":"P\u00e1l","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"R.","family":"Ravi","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Amitabh","family":"Sinha","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2011,9,27]]},"reference":[{"key":"R1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539792236237"},{"key":"R2","doi-asserted-by":"crossref","unstructured":"B. M. Anthony and A. Gupta,\n                      Infrastructure leasing problems\n                      , in Proceedings of the 12th Integer Programming and Combinatorial Optimization Conference (IPCO), Ithaca, NY, 2007, Lecture Notes in Comput. Sci. 4513, Springer, New York, 2007, pp. 424\u2013438.","DOI":"10.1007\/978-3-540-72792-7_32"},{"key":"R3","doi-asserted-by":"crossref","first-page":"173","DOI":"10.1111\/j.2517-6161.1955.tb00191.x","volume":"17","author":"Beale E. M.","year":"1955","journal-title":"J. Roy. Statist. Soc. Ser. B."},{"key":"R4","unstructured":"J. R. Birge and F. Louveaux,\n                      Introduction to Stochastic Programming\n                      , Springer-Verlag, New York, Berlin, 1997."},{"key":"R5","doi-asserted-by":"crossref","unstructured":"M. Charikar, C. Chekuri, and M. P\u00e1l,\n                      Sampling bounds for stochastic optimization\n                      , in Approximation, Randomization and Combinatorial Optimization, Lecture Notes in Comput. Sci. 3624, Springer, Berlin, 2005, pp. 257\u2013269.","DOI":"10.1007\/11538462_22"},{"key":"R6","unstructured":"M. Chleb\u00edk and J. Chleb\u00edkov\u00e1,\n                      Approximation hardness of the Steiner tree problem on graphs\n                      , in Proceedings of the 8th Scandinavian Workshop on Algorithm Theory, Turku, Finland, 2002, Lecture Notes in Comput. Sci. 2368, Springer, New York, 2002, pp. 95\u201399."},{"key":"R7","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.1.3-4.197"},{"key":"R8","doi-asserted-by":"publisher","DOI":"10.1016\/j.dss.2004.08.004"},{"key":"R9","doi-asserted-by":"publisher","DOI":"10.1002\/nav.10092"},{"key":"R10","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-005-0597-0"},{"key":"R11","doi-asserted-by":"publisher","DOI":"10.1137\/090767108"},{"key":"R12","unstructured":"N. Garg, A. Gupta, S. Leonardi, and P. Sankowski,\n                      Stochastic analyses for online combinatorial optimization problems\n                      , in Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, San Francisco, 2008, pp. 942\u2013951."},{"key":"R13","doi-asserted-by":"crossref","unstructured":"A. Goel and P. Indyk,\n                      Stochastic load balancing and related problems\n                      , in Proceedings of the 40th Annual Symposium on Foundations of Computer Science, New York, 1999, IEEE Computer Society Press, Piscataway, NJ, 1999, pp. 579\u2013586.","DOI":"10.1109\/SFFCS.1999.814632"},{"key":"R14","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793242618"},{"key":"R15","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1998.0993"},{"key":"R16","doi-asserted-by":"publisher","DOI":"10.1145\/1236457.1236458"},{"key":"R17","doi-asserted-by":"crossref","unstructured":"A. Gupta and M. P\u00e1l,\n                      Stochastic Steiner trees without a root\n                      , in Proceedings of the 32nd International Colloquium on Automata, Languages and Programming (ICALP), Lecture Notes in Comput. Sci. 3580, Springer, New York, 2005, pp. 1051\u20131063.","DOI":"10.1007\/11523468_85"},{"key":"R18","doi-asserted-by":"crossref","unstructured":"A. Gupta, M. P\u00e1l, R. Ravi, and A. Sinha,\n                      Boosted sampling: Approximation algorithms for stochastic optimization\n                      , in Proceedings of the 36th Annual ACM Symposium on Theory of Computing, Chicago, ACM, New York, 2004, pp. 417\u2013425.","DOI":"10.1145\/1007352.1007419"},{"key":"R19","doi-asserted-by":"crossref","unstructured":"A. Gupta, M. P\u00e1l, R. Ravi, and A. Sinha,\n                      What about Wednesday? Approximation algorithms for multistage stochastic optimization\n                      , in Proceedings of the International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX), Berkeley, CA, 2005, Lecture Notes in Comput. Sci. 3624, Springer, New York, 2005, pp. 86\u201398.","DOI":"10.1007\/11538462_8"},{"key":"R20","doi-asserted-by":"publisher","DOI":"10.1287\/moor.1060.0237"},{"key":"R21","doi-asserted-by":"publisher","DOI":"10.1145\/502090.502098"},{"key":"R22","unstructured":"A. Hayrapetyan, C. Swamy, and E. Tardos,\n                      Network design for information networks\n                      , in Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, Vancouver, BC, 2005, pp. 933\u2013942."},{"key":"R23","unstructured":"N. Immorlica, D. Karger, M. Minkoff, and V. S. Mirrokni,\n                      On the costs and benefits of procrastination: Approximation algorithms for stochastic combinatorial optimization problems\n                      , in Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, New Orleans, LA, 2004, pp. 684\u2013693."},{"key":"R24","doi-asserted-by":"crossref","unstructured":"N. Immorlica, M. Mahdian, and V. Mirrokni,\n                      Limitations of cross-monotonic cost-sharing schemes\n                      , ACM Trans. Algorithms, 4 (2008), 24.","DOI":"10.1145\/1361192.1361201"},{"key":"R25","doi-asserted-by":"crossref","unstructured":"K. Jain and V. Vazirani,\n                      Applications of approximation algorithms to cooperative games\n                      , in Proceedings of the 33rd Annual ACM Symposium on the Theory of Computing (STOC), Heraklion, Greece, 2001, ACM, New York, pp. 364\u2013372.","DOI":"10.1145\/380752.380825"},{"key":"R26","doi-asserted-by":"publisher","DOI":"10.1137\/060658448"},{"key":"R27","unstructured":"P. Kall and S. W. Wallace,\n                      Stochastic Programming\n                      , John Wiley & Sons, New York, 1994."},{"key":"R28","doi-asserted-by":"publisher","DOI":"10.1023\/A:1018930113099"},{"key":"R29","unstructured":"W. K. Klein Haneveld and M. H. van der Vlerk,\n                      Stochastic Programming\n                      , unpublished textbook, Department of Econometrics and Operations Research, University of Groningen, The Netherlands, 2003."},{"key":"R30","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539797329142"},{"key":"R31","doi-asserted-by":"publisher","DOI":"10.1137\/S1052623499363220"},{"key":"R32","doi-asserted-by":"publisher","DOI":"10.1137\/050646408"},{"key":"R33","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539701383443"},{"key":"R34","doi-asserted-by":"publisher","DOI":"10.1145\/331524.331530"},{"key":"R35","doi-asserted-by":"publisher","DOI":"10.1007\/PL00004200"},{"key":"R36","doi-asserted-by":"crossref","unstructured":"M. P\u00e1l and E. Tardos,\n                      Group strategyproof mechanisms via primal-dual algorithms\n                      , in Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, Cambridge, MA, 2003, IEEE Computer Society Press, Piscataway, NJ, 2003, pp. 584\u2013593.","DOI":"10.1109\/SFCS.2003.1238231"},{"key":"R37","unstructured":"M. Pinedo,\n                      Scheduling: Theory, Algorithms, and Systems\n                      , Prentice\u2013Hall, Englewood Cliffs, NJ, 1995."},{"key":"R38","doi-asserted-by":"publisher","DOI":"10.1002\/j.1538-7305.1957.tb01515.x"},{"key":"R39","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-005-0673-5"},{"key":"R40","unstructured":"G. Robins and A. Zelikovsky,\n                      Improved Steiner tree approximation in graphs\n                      , in Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2000, pp. 770\u2013779."},{"key":"R41","doi-asserted-by":"publisher","DOI":"10.1111\/j.1467-9574.1996.tb01506.x"},{"key":"R42","doi-asserted-by":"publisher","DOI":"10.1145\/1217856.1217860"},{"key":"R43","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539702415007"},{"key":"R44","unstructured":"A. Srinivasan,\n                      Approximation algorithms for stochastic and risk-averse optimization\n                      , in Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, New Orleans, LA, 2007, pp. 1305\u20131313."},{"key":"R45","doi-asserted-by":"crossref","unstructured":"C. Swamy and D. Shmoys,\n                      Sampling-based approximation algorithms for multi-stage stochastic optimization\n                      , in Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, Pittsburgh, PA, 2005, IEEE Computer Society Press, Piscataway, NJ, 2005, pp. 357\u2013366.","DOI":"10.1109\/SFCS.2005.67"},{"key":"R46","doi-asserted-by":"publisher","DOI":"10.1145\/1122480.1122493"},{"key":"R47","unstructured":"V. V. Vazirani,\n                      Approximation Algorithms\n                      , Springer-Verlag, Berlin, 2001."},{"key":"R48","doi-asserted-by":"crossref","unstructured":"H. P. Young,\n                      Cost allocation\n                      , in Handbook of Game Theory, R. J. Aumann and S. Hart, eds., North\u2013Holland, Amsterdam, 1994, Vol. 2, Chapter 34, pp. 1193\u20131235.","DOI":"10.1016\/S1574-0005(05)80066-9"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/080732250","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:35:51Z","timestamp":1787337351000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/080732250"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,1]]},"references-count":48,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2011,1]]}},"alternative-id":["10.1137\/080732250"],"URL":"https:\/\/doi.org\/10.1137\/080732250","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,1]]}}}