{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,28]],"date-time":"2026-03-28T06:18:13Z","timestamp":1774678693777,"version":"3.50.1"},"reference-count":31,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2011,4,9]],"date-time":"2011-04-09T00:00:00Z","timestamp":1302307200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2012,8]]},"DOI":"10.1007\/s00453-011-9511-8","type":"journal-article","created":{"date-parts":[[2011,4,8]],"date-time":"2011-04-08T18:34:11Z","timestamp":1302287651000},"page":"733-762","source":"Crossref","is-referenced-by-count":52,"title":["When LP Is the Cure for Your Matching Woes: Improved Bounds for Stochastic Matchings"],"prefix":"10.1007","volume":"63","author":[{"given":"Nikhil","family":"Bansal","sequence":"first","affiliation":[]},{"given":"Anupam","family":"Gupta","sequence":"additional","affiliation":[]},{"given":"Jian","family":"Li","sequence":"additional","affiliation":[]},{"given":"Juli\u00e1n","family":"Mestre","sequence":"additional","affiliation":[]},{"given":"Viswanath","family":"Nagarajan","sequence":"additional","affiliation":[]},{"given":"Atri","family":"Rudra","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2011,4,9]]},"reference":[{"key":"9511_CR1","unstructured":"Adamczyk, M.: Greedy algorithm for stochastic matching is a 2-approximation. arXiv:1007.3036 (2010)"},{"key":"9511_CR2","doi-asserted-by":"crossref","DOI":"10.1002\/9780470277331","volume-title":"The Probabilistic Method","author":"N. Alon","year":"2008","unstructured":"Alon, N., Spencer, J.H.: The Probabilistic Method. Wiley-Interscience, New York (2008)"},{"key":"9511_CR3","series-title":"LNCS","first-page":"170","volume-title":"Proceedings of the 18th European Symposium on Algorithms","author":"B. Bahmani","year":"2010","unstructured":"Bahmani, B., Kapralov, M.: Improved bounds for online stochastic matching. In: Proceedings of the 18th European Symposium on Algorithms. LNCS, vol.\u00a06346, pp. 170\u2013181. Springer, Berlin (2010)"},{"key":"9511_CR4","series-title":"LNCS","first-page":"218","volume-title":"Proceedings of the 18th European Symposium on Algorithms","author":"N. Bansal","year":"2010","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. In: Proceedings of the 18th European Symposium on Algorithms. LNCS, vol.\u00a06346, pp. 218\u2013229. Springer, Berlin (2010)"},{"key":"9511_CR5","series-title":"LNCS","doi-asserted-by":"crossref","first-page":"369","DOI":"10.1007\/978-3-642-13036-6_28","volume-title":"Proceedings of the 14th Conference on Integer Programming and Combinatorial Optimization","author":"N. Bansal","year":"2010","unstructured":"Bansal, N., Korula, N., Nagarajan, V., Srinivasan, A.: On k-column sparse packing programs. In: Proceedings of the 14th Conference on Integer Programming and Combinatorial Optimization. LNCS, vol.\u00a06080, pp.\u00a0369\u2013382 (2010)"},{"key":"9511_CR6","first-page":"379","volume-title":"Proceedings of the 41st ACM Symposium on Theory of Computing","author":"S. Bhattacharya","year":"2010","unstructured":"Bhattacharya, S., Goel, G., Gollapudi, S., Munagala, K.: Budget constrained auctions with heterogeneous items. In: Proceedings of the 41st ACM Symposium on Theory of Computing, pp.\u00a0379\u2013388. ACM, New York (2010)"},{"issue":"1","key":"9511_CR7","doi-asserted-by":"crossref","first-page":"80","DOI":"10.1145\/1360443.1360462","volume":"39","author":"B.E. Birnbaum","year":"2008","unstructured":"Birnbaum, B.E., Mathieu, C.: On-line bipartite matching made simple. SIGACT News 39(1), 80\u201387 (2008)","journal-title":"SIGACT News"},{"issue":"3","key":"9511_CR8","doi-asserted-by":"crossref","first-page":"343","DOI":"10.1002\/rsa.10033","volume":"20","author":"R. Carr","year":"2002","unstructured":"Carr, R., Vempala, S.: Randomized metarounding. Random Struct. Algorithms 20(3), 343\u2013352 (2002). Probabilistic methods in combinatorial optimization","journal-title":"Random Struct. Algorithms"},{"key":"9511_CR9","series-title":"LNCS","doi-asserted-by":"crossref","first-page":"266","DOI":"10.1007\/978-3-642-02927-1_23","volume-title":"Proceedings of the 36th International Colloquium on Automata, Languages and Programming","author":"N. Chen","year":"2009","unstructured":"Chen, N., Immorlica, N., Karlin, A.R., Mahdian, M., Rudra, A.: Approximating matches made in heaven. In: Proceedings of the 36th International Colloquium on Automata, Languages and Programming. LNCS, vol.\u00a05555, pp. 266\u2013278 (2009)"},{"key":"9511_CR10","first-page":"395","volume-title":"Proceedings of the 16th Annual ACM\u2013SIAM Symposium on Discrete Algorithms","author":"B.C. Dean","year":"2005","unstructured":"Dean, B.C., Goemans, M.X., Vondr\u00e1k, J.: Adaptivity and approximation for stochastic packing problems. In: Proceedings of the 16th Annual ACM\u2013SIAM Symposium on Discrete Algorithms, pp. 395\u2013404 (2005)"},{"issue":"4","key":"9511_CR11","doi-asserted-by":"crossref","first-page":"945","DOI":"10.1287\/moor.1080.0330","volume":"33","author":"B.C. 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":"9511_CR12","doi-asserted-by":"crossref","first-page":"117","DOI":"10.1109\/FOCS.2009.72","volume-title":"Proceedings of the 50th Annual Symposium on Foundations of Computer Science","author":"J. Feldman","year":"2009","unstructured":"Feldman, J., Mehta, A., Mirrokni, V.S., Muthukrishnan, S.: Online stochastic matching: beating 1\u22121\/e.\u00a0In: Proceedings of the 50th Annual Symposium on Foundations of Computer Science, pp.\u00a0117\u2013126. IEEE, New York (2009)"},{"issue":"2","key":"9511_CR13","doi-asserted-by":"crossref","first-page":"167","DOI":"10.1007\/BF01303202","volume":"13","author":"Z. F\u00fcredi","year":"1993","unstructured":"F\u00fcredi, Z., Kahn, J., Seymour, P.: On the fractional matching polytope of a hypergraph. Combinatorica 13(2), 167\u2013180 (1993)","journal-title":"Combinatorica"},{"issue":"3","key":"9511_CR14","doi-asserted-by":"crossref","first-page":"360","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 53(3), 360 (2006)","journal-title":"J. ACM"},{"key":"9511_CR15","first-page":"982","volume-title":"Proceedings of the 19th Annual ACM\u2013SIAM Symposium on Discrete Algorithms","author":"G. Goel","year":"2008","unstructured":"Goel, G., Mehta, A.: Online budgeted matching in random input models with applications to adwords. In: Proceedings of the 19th Annual ACM\u2013SIAM Symposium on Discrete Algorithms, pp. 982\u2013991 (2008)"},{"key":"9511_CR16","first-page":"483","volume-title":"Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science","author":"S. Guha","year":"2007","unstructured":"Guha, S., Munagala, K.: Approximation algorithms for partial-information based stochastic control with Markovian rewards. In: Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science, pp. 483\u2013493 (2007)"},{"key":"9511_CR17","series-title":"LNCS","doi-asserted-by":"crossref","first-page":"496","DOI":"10.1007\/978-3-642-02930-1_41","volume-title":"Proceedings of the 36th International Colloquium on Automata, Languages and Programming","author":"S. Guha","year":"2009","unstructured":"Guha, S., Munagala, K.: Multi-armed bandits with metric switching costs. In: Proceedings of the 36th International Colloquium on Automata, Languages and Programming. LNCS, vol.\u00a05555, pp. 496\u2013507 (2009)"},{"key":"9511_CR18","doi-asserted-by":"crossref","unstructured":"Gupta, A., Krishnaswamy, R., Molinaro, M., Ravi, R.: Approximation algorithms for correlated knapsacks and non-martingale bandits. CoRR, abs\/1102.3749 (2011)","DOI":"10.1109\/FOCS.2011.48"},{"key":"9511_CR19","first-page":"417","volume-title":"Proceedings of the 36th ACM Symposium on Theory of Computing","author":"A. Gupta","year":"2004","unstructured":"Gupta, A., P\u00e1l, M., Ravi, R., Sinha, A.: Boosted sampling: approximation algorithms for stochastic optimization. In: Proceedings of the 36th ACM Symposium on Theory of Computing, pp.\u00a0417\u2013426. ACM, New York (2004)"},{"issue":"1","key":"9511_CR20","doi-asserted-by":"crossref","first-page":"20","DOI":"10.1007\/s00037-006-0205-6","volume":"15","author":"E. Hazan","year":"2006","unstructured":"Hazan, E., Safra, S., Schwartz, O.: On the complexity of approximating k-set packing. Comput. Complex. 15(1), 20\u201339 (2006)","journal-title":"Comput. Complex."},{"issue":"1","key":"9511_CR21","doi-asserted-by":"crossref","first-page":"68","DOI":"10.1137\/0402008","volume":"2","author":"C. Hurkens","year":"1989","unstructured":"Hurkens, C., Schrijver, A.: On the size of systems of sets every t of which have an SDR, with an application to the worst-case ratio of heuristics for packing problems. SIAM J. Discrete Math. 2(1), 68\u201372 (1989)","journal-title":"SIAM J. Discrete Math."},{"issue":"3","key":"9511_CR22","doi-asserted-by":"crossref","first-page":"478","DOI":"10.1006\/jagm.1993.1026","volume":"14","author":"B. Kalyanasundaram","year":"1993","unstructured":"Kalyanasundaram, B., Pruhs, K.: Online weighted matching. J. Algorithms 14(3), 478\u2013488 (1993)","journal-title":"J. Algorithms"},{"key":"9511_CR23","first-page":"352","volume-title":"Proceedings of the 22nd Annual ACM Symposium on Theory of Computing","author":"R.M. Karp","year":"1990","unstructured":"Karp, R.M., Vazirani, U.V., Vazirani, V.V.: An optimal algorithm for online bipartite matching. In: Proceedings of the 22nd Annual ACM Symposium on Theory of Computing, pp.\u00a0352\u2013358. ACM, New York (1990)"},{"issue":"2\u20133","key":"9511_CR24","doi-asserted-by":"crossref","first-page":"213","DOI":"10.1016\/j.tcs.2008.08.010","volume":"408","author":"I. Katriel","year":"2008","unstructured":"Katriel, I., Kenyon-Mathieu, C., Upfal, E.: Commitment under uncertainty: two-stage stochastic matching problems. Theor. Comput. Sci. 408(2\u20133), 213\u2013223 (2008)","journal-title":"Theor. Comput. Sci."},{"key":"9511_CR25","doi-asserted-by":"crossref","first-page":"288","DOI":"10.1145\/1250910.1250952","volume-title":"Proceedings of the 8th ACM Conference on Electronic Commerce","author":"M. Mahdian","year":"2007","unstructured":"Mahdian, M., Nazerzadeh, H., Saberi, A.: Allocating online advertisement space with unreliable estimates. In: Proceedings of the 8th ACM Conference on Electronic Commerce, pp. 288\u2013294 (2007)"},{"key":"9511_CR26","volume-title":"Proceedings of the 22th Annual ACM\u2013SIAM Symposium on Discrete Algorithms","author":"V.H. Manshadi","year":"2011","unstructured":"Manshadi, V.H., Gharan, S.O., Saberi, A.: Online stochastic matching: Online actions based on offline statistics. In: Proceedings of the 22th Annual ACM\u2013SIAM Symposium on Discrete Algorithms (2011)"},{"key":"9511_CR27","first-page":"264","volume-title":"Proceedings of the 46th Annual Symposium on Foundations of Computer Science","author":"A. Mehta","year":"2005","unstructured":"Mehta, A., Saberi, A., Vazirani, U.V., Vazirani, V.V.: Adwords and generalized on-line matching. In: Proceedings of the 46th Annual Symposium on Foundations of Computer Science, pp. 264\u2013273 (2005)"},{"key":"9511_CR28","volume-title":"Combinatorial Optimization","author":"A. Schrijver","year":"2003","unstructured":"Schrijver, A.: Combinatorial Optimization. Springer, Berlin (2003)"},{"issue":"3","key":"9511_CR29","doi-asserted-by":"crossref","first-page":"488","DOI":"10.1137\/S0895480102419731","volume":"18","author":"H. Shachnai","year":"2005","unstructured":"Shachnai, H., Srinivasan, A.: Finding large independent sets in graphs and hypergraphs. SIAM J. Discrete Math. 18(3), 488\u2013500 (2005)","journal-title":"SIAM J. Discrete Math."},{"issue":"6","key":"9511_CR30","doi-asserted-by":"crossref","first-page":"978","DOI":"10.1145\/1217856.1217860","volume":"53","author":"D. Shmoys","year":"2006","unstructured":"Shmoys, D., Swamy, C.: An approximation scheme for stochastic linear programming and its application to stochastic integer programs. J. ACM 53(6), 978\u20131012 (2006)","journal-title":"J. ACM"},{"issue":"1","key":"9511_CR31","doi-asserted-by":"crossref","first-page":"46","DOI":"10.1145\/1122480.1122493","volume":"37","author":"C. Swamy","year":"2006","unstructured":"Swamy, C., Shmoys, D.: Approximation algorithms for 2-stage stochastic optimization problems. SIGACT News 37(1), 46 (2006)","journal-title":"SIGACT News"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-011-9511-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-011-9511-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-011-9511-8","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,9]],"date-time":"2019-06-09T17:58:52Z","timestamp":1560103132000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-011-9511-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,4,9]]},"references-count":31,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2012,8]]}},"alternative-id":["9511"],"URL":"https:\/\/doi.org\/10.1007\/s00453-011-9511-8","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,4,9]]}}}