{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,11]],"date-time":"2025-12-11T20:49:15Z","timestamp":1765486155335,"version":"3.37.3"},"reference-count":26,"publisher":"Springer Science and Business Media LLC","issue":"11","license":[{"start":{"date-parts":[[2017,10,23]],"date-time":"2017-10-23T00:00:00Z","timestamp":1508716800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2017,10,23]],"date-time":"2017-10-23T00:00:00Z","timestamp":1508716800000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/100000140","name":"United States Department of Transportation","doi-asserted-by":"crossref","award":["49198-25-26"],"award-info":[{"award-number":["49198-25-26"]}],"id":[{"id":"10.13039\/100000140","id-type":"DOI","asserted-by":"crossref"}]},{"name":"British Council\u2019s UKIERI research program."},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["1010789","1422569"],"award-info":[{"award-number":["1010789","1422569"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["1010789"],"award-info":[{"award-number":["1010789"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100004344","name":"Adobe Systems","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100004344","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2018,11]]},"DOI":"10.1007\/s00453-017-0383-4","type":"journal-article","created":{"date-parts":[[2017,10,23]],"date-time":"2017-10-23T23:41:23Z","timestamp":1508802083000},"page":"3225-3252","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":11,"title":["Improved Bounds in Stochastic Matching and Optimization"],"prefix":"10.1007","volume":"80","author":[{"given":"Alok","family":"Baveja","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Amit","family":"Chavan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Andrei","family":"Nikiforov","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Aravind","family":"Srinivasan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pan","family":"Xu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2017,10,23]]},"reference":[{"unstructured":"Abolhassani, M., Esfandiari, H., Hajiaghayi, M., Mahini, H., Malec, D., Srinivasan, A.: Selling tomorrow\u2019s bargains today. In: Proceedings of the 2015 International Conference on Autonomous Agents and Multiagent Systems, International Foundation for Autonomous Agents and Multiagent Systems, pp. 337\u2013345 (2015)","key":"383_CR1"},{"doi-asserted-by":"crossref","unstructured":"Adamczyk, M., Grandoni, F., Mukherjee, J.: Improved approximation algorithms for stochastic matching. In: Bansal, N., Finocchi, I. (eds.) Algorithms\u2014ESA 2015. Lecture Notes in Computer Science, vol. 9294. Springer, Berlin, Heidelberg (2015)","key":"383_CR2","DOI":"10.1007\/978-3-662-48350-3_1"},{"unstructured":"Alon, N., Spencer, J.H.: Wiley interscience series in discrete mathematics and optimization. In: The Probabilistic Method, vol. 6, pp. 85\u201396 (2008)","key":"383_CR3"},{"doi-asserted-by":"crossref","unstructured":"Bansal, N., Gupta, A., Nagarajan, V., Rudra, A.: When lp is the cure for your matching woes: approximating stochastic matchings. arXiv preprint arXiv:1003.0167v1 [cs DS] (2010)","key":"383_CR4","DOI":"10.1007\/978-3-642-15781-3_19"},{"issue":"4","key":"383_CR5","doi-asserted-by":"publisher","first-page":"733","DOI":"10.1007\/s00453-011-9511-8","volume":"63","author":"N Bansal","year":"2012","unstructured":"Bansal, N., Gupta, A., Li, J., Mestre, J., Nagarajan, V., Rudra, A.: When LP is the cure for your matching woes: improved bounds for stochastic matchings. Algorithmica 63(4), 733\u2013762 (2012)","journal-title":"Algorithmica"},{"key":"383_CR6","doi-asserted-by":"crossref","first-page":"173","DOI":"10.1111\/j.2517-6161.1955.tb00191.x","volume":"17","author":"EM Beale","year":"1955","unstructured":"Beale, E.M.: On minimizing a convex function subject to linear inequalities. J. Roy. Stat. Soc. B Met. 17, 173\u2013184 (1955)","journal-title":"J. Roy. Stat. Soc. B Met."},{"key":"383_CR7","volume-title":"Introduction to Stochastic Programming","author":"JR Birge","year":"1997","unstructured":"Birge, J.R., Louveaux, F.: Introduction to Stochastic Programming. Springer, New York (1997)"},{"doi-asserted-by":"crossref","unstructured":"Chen, N., Immorlica, N., Karlin, A.R., Mahdian, M., Rudra, A.: Approximating matches made in heaven. In: Albers, S., Marchetti-Spaccamela, A., Matias, Y., Nikoletseas, S., Thomas, W. (eds.) Automata, Languages and Programming. ICALP 2009. Lecture Notes in Computer Science, vol. 5555. Springer, Berlin, Heidelberg (2009)","key":"383_CR8","DOI":"10.1007\/978-3-642-02927-1_23"},{"issue":"3\u20134","key":"383_CR9","doi-asserted-by":"publisher","first-page":"197","DOI":"10.1287\/mnsc.1.3-4.197","volume":"1","author":"GB Dantzig","year":"1955","unstructured":"Dantzig, G.B.: Linear programming under uncertainty. Manag. Sci. 1(3\u20134), 197\u2013206 (1955)","journal-title":"Manag. Sci."},{"issue":"4","key":"383_CR10","doi-asserted-by":"publisher","first-page":"945","DOI":"10.1287\/moor.1080.0330","volume":"33","author":"BC Dean","year":"2008","unstructured":"Dean, B.C., Goemans, M.X., Vondr\u00e1k, J.: Approximating the stochastic knapsack problem: the benefit of adaptivity. Math. Oper. Res. 33(4), 945\u2013964 (2008)","journal-title":"Math. Oper. Res."},{"key":"383_CR11","doi-asserted-by":"publisher","first-page":"89","DOI":"10.1007\/BF01651330","volume":"22","author":"CM Fortuin","year":"1971","unstructured":"Fortuin, C.M., Ginibre, J., Kasteleyn, P.N.: Correlational inequalities for partially ordered sets. Commun. Math. Phys. 22, 89\u2013103 (1971)","journal-title":"Commun. Math. Phys."},{"issue":"2","key":"383_CR12","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1007\/BF01303202","volume":"13","author":"Z F\u00fcredi","year":"1993","unstructured":"F\u00fcredi, Z., Kahn, J., Seymour, P.D.: On the fractional matching polytope of a hypergraph. Combinatorica 13(2), 167\u2013180 (1993)","journal-title":"Combinatorica"},{"issue":"3","key":"383_CR13","doi-asserted-by":"publisher","first-page":"324","DOI":"10.1145\/1147954.1147956","volume":"53","author":"R Gandhi","year":"2006","unstructured":"Gandhi, R., Khuller, S., Parthasarathy, S., Srinivasan, A.: Dependent rounding and its applications to approximation algorithms. J. ACM (JACM) 53(3), 324\u2013360 (2006)","journal-title":"J. ACM (JACM)"},{"unstructured":"Garg, N., Gupta, A., Leonardi, S., Sankowski, P.: Stochastic analyses for online combinatorial optimization problems. In: Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, Society for Industrial and Applied Mathematics, pp. 942\u2013951 (2008)","key":"383_CR14"},{"doi-asserted-by":"crossref","unstructured":"Gupta, A., Kumar, A.: A constant-factor approximation for stochastic steiner forest. In: Proceedings of the Forty-First Annual ACM Symposium on Theory of Computing, pp 659\u2013668. ACM (2009)","key":"383_CR15","DOI":"10.1145\/1536414.1536504"},{"issue":"2","key":"383_CR16","doi-asserted-by":"publisher","first-page":"345","DOI":"10.1287\/moor.1060.0237","volume":"32","author":"A Gupta","year":"2007","unstructured":"Gupta, A., Ravi, R., Sinha, A.: LP rounding approximation algorithms for stochastic network design. Math. Oper. Res. 32(2), 345\u2013364 (2007)","journal-title":"Math. Oper. Res."},{"unstructured":"Immorlica, N., Karger, D., Minkoff, M., Mirrokni, V.S.: On the costs and benefits of procrastination: approximation algorithms for stochastic combinatorial optimization problems. In: Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, Society for Industrial and Applied Mathematics, pp 691\u2013700 (2004)","key":"383_CR17"},{"issue":"2","key":"383_CR18","doi-asserted-by":"publisher","first-page":"284","DOI":"10.1287\/moor.1060.0205","volume":"32","author":"R Levi","year":"2007","unstructured":"Levi, R., P\u00e1l, M., Roundy, R.O., Shmoys, D.B.: Approximation algorithms for stochastic inventory control models. Math. Oper. Res. 32(2), 284\u2013302 (2007)","journal-title":"Math. Oper. Res."},{"issue":"1","key":"383_CR19","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1007\/s10107-005-0673-5","volume":"108","author":"R Ravi","year":"2006","unstructured":"Ravi, R., Sinha, A.: Hedging uncertainty: approximation algorithms for stochastic optimization problems. Math. Program. 108(1), 97\u2013114 (2006)","journal-title":"Math. Program."},{"key":"383_CR20","volume-title":"Stochastic Programming","author":"AP Ruszczynski","year":"2003","unstructured":"Ruszczynski, A.P., Shapiro, A.: Stochastic Programming, vol. 10. Elsevier, Amsterdam (2003)"},{"key":"383_CR21","doi-asserted-by":"publisher","first-page":"488","DOI":"10.1137\/S0895480102419731","volume":"18","author":"H Shachnai","year":"2004","unstructured":"Shachnai, H., Srinivasan, A.: Finding large independent sets in graphs and hypergraphs. SIAM J. Discret. Math. 18, 488\u2013500 (2004)","journal-title":"SIAM J. Discret. Math."},{"key":"383_CR22","doi-asserted-by":"crossref","DOI":"10.1137\/1.9781611973433","volume-title":"Lectures on Stochastic Programming\u2014Modeling and Theory","author":"A Shapiro","year":"2014","unstructured":"Shapiro, A., Dentcheva, D., Ruszczynski, A.: Lectures on Stochastic Programming\u2014Modeling and Theory, vol. 16, 2nd edn. SIAM, Philadelphia (2014)","edition":"2"},{"issue":"6","key":"383_CR23","doi-asserted-by":"publisher","first-page":"978","DOI":"10.1145\/1217856.1217860","volume":"53","author":"DB Shmoys","year":"2006","unstructured":"Shmoys, D.B., Swamy, C.: An approximation scheme for stochastic linear programming and its application to stochastic integer programs. J. ACM (JACM) 53(6), 978\u20131012 (2006)","journal-title":"J. ACM (JACM)"},{"unstructured":"Srinivasan, A.: Approximation algorithms for stochastic and risk-averse optimization. In: Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pp 1305\u20131313. Society for Industrial and Applied Mathematics (2007)","key":"383_CR24"},{"key":"383_CR25","volume-title":"Approximation Algorithms","author":"VV Vazirani","year":"2013","unstructured":"Vazirani, V.V.: Approximation Algorithms. Springer, Berlin (2013)"},{"key":"383_CR26","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511921735","volume-title":"The Design of Approximation Algorithms","author":"DP Williamson","year":"2011","unstructured":"Williamson, D.P., Shmoys, D.B.: The Design of Approximation Algorithms. Cambridge University Press, Cambridge (2011)"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-017-0383-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-017-0383-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-017-0383-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,6,27]],"date-time":"2024-06-27T23:41:25Z","timestamp":1719531685000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-017-0383-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,10,23]]},"references-count":26,"journal-issue":{"issue":"11","published-print":{"date-parts":[[2018,11]]}},"alternative-id":["383"],"URL":"https:\/\/doi.org\/10.1007\/s00453-017-0383-4","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2017,10,23]]},"assertion":[{"value":"15 July 2016","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"12 October 2017","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"23 October 2017","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}