{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T00:00:17Z","timestamp":1740096017278,"version":"3.37.3"},"publisher-location":"Berlin, Heidelberg","reference-count":20,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642157806"},{"type":"electronic","value":"9783642157813"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2010]]},"DOI":"10.1007\/978-3-642-15781-3_19","type":"book-chapter","created":{"date-parts":[[2010,9,1]],"date-time":"2010-09-01T11:40:03Z","timestamp":1283341203000},"page":"218-229","source":"Crossref","is-referenced-by-count":12,"title":["When LP Is the Cure for Your Matching Woes: Improved Bounds for Stochastic Matchings"],"prefix":"10.1007","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","reference":[{"key":"19_CR1","doi-asserted-by":"crossref","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. arXiv (2010)","DOI":"10.1007\/978-3-642-15781-3_19"},{"key":"19_CR2","unstructured":"Bhattacharya, S., Goel, G., Gollapudi, S., Munagala, K.: Budget constrained auctions with heterogeneous items. In: STOC (2009), arxiv:abs\/0907.4166"},{"issue":"1","key":"19_CR3","doi-asserted-by":"publisher","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\u00a039(1), 80\u201387 (2008)","journal-title":"SIGACT News"},{"key":"19_CR4","doi-asserted-by":"crossref","unstructured":"Chen, N., Immorlica, N., Karlin, A.R., Mahdian, M., Rudra, A.: Approximating matches made in heaven. In: ICALP, Part I, \u00a0vol. (1), pp. 266\u2013278 (2009)","DOI":"10.1007\/978-3-642-02927-1_23"},{"key":"19_CR5","unstructured":"Dean, B.C., Goemans, M.X., Vondr\u00e1k, J.: Adaptivity and approximation for stochastic packing problems. In: SODA, pp. 395\u2013404 (2005)"},{"issue":"4","key":"19_CR6","doi-asserted-by":"publisher","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.\u00a033(4), 945\u2013964 (2008), http:\/\/dx.doi.org\/10.1287\/moor.1080.0330","journal-title":"Math. Oper. Res."},{"key":"19_CR7","unstructured":"Feldman, J., Mehta, A., Mirrokni, V.S., Muthukrishnan, S.: Online stochastic matching: Beating 1 \u2212 1\/e. In: FOCS (2009), Arxiv:abs\/0905.4100"},{"key":"19_CR8","unstructured":"Goel, G., Mehta, A.: Online budgeted matching in random input models with applications to adwords. In: SODA, pp. 982\u2013991 (2008)"},{"key":"19_CR9","doi-asserted-by":"crossref","unstructured":"Guha, S., Munagala, K.: Approximation algorithms for partial-information based stochastic control with markovian rewards. In: FOCS, pp. 483\u2013493 (2007)","DOI":"10.1109\/FOCS.2007.23"},{"key":"19_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"496","DOI":"10.1007\/978-3-642-02930-1_41","volume-title":"Automata, Languages and Programming","author":"S. Guha","year":"2009","unstructured":"Guha, S., Munagala, K.: Multi-armed bandits with metric switching costs. In: Albers, S., Marchetti-Spaccamela, A., Matias, Y., Nikoletseas, S., Thomas, W. (eds.) ICALP 2009. LNCS, vol.\u00a05556, pp. 496\u2013507. Springer, Heidelberg (2009)"},{"key":"19_CR11","doi-asserted-by":"crossref","first-page":"417","DOI":"10.1145\/1007352.1007419","volume-title":"STOC","author":"A. Gupta","year":"2004","unstructured":"Gupta, A., P\u00e1l, M., Ravi, R., Sinha, A.: Boosted sampling: approximation algorithms for stochastic optimization. In: STOC, pp. 417\u2013426. ACM, New York (2004)"},{"issue":"3","key":"19_CR12","doi-asserted-by":"publisher","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\u00a014(3), 478\u2013488 (1993)","journal-title":"J. Algorithms"},{"key":"19_CR13","doi-asserted-by":"crossref","unstructured":"Karp, R.M., Vazirani, U.V., Vazirani, V.V.: An optimal algorithm for on-line bipartite matching. In: STOC, pp. 352\u2013358 (1990)","DOI":"10.1145\/100216.100262"},{"issue":"2-3","key":"19_CR14","doi-asserted-by":"publisher","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. Theoretical Computer Science\u00a0408(2-3), 213\u2013223 (2008)","journal-title":"Theoretical Computer Science"},{"key":"19_CR15","doi-asserted-by":"crossref","unstructured":"Mahdian, M., Nazerzadeh, H., Saberi, A.: Allocating online advertisement space with unreliable estimates. In: EC. p. 294 (2007)","DOI":"10.1145\/1250910.1250952"},{"key":"19_CR16","doi-asserted-by":"crossref","unstructured":"Mehta, A., Saberi, A., Vazirani, U.V., Vazirani, V.V.: Adwords and generalized on-line matching. In: FOCS, pp. 264\u2013273 (2005)","DOI":"10.1109\/SFCS.2005.12"},{"key":"19_CR17","volume-title":"Combinatorial Optimization","author":"A. Schrijver","year":"2003","unstructured":"Schrijver, A.: Combinatorial Optimization. Springer, Heidelberg (2003)"},{"key":"19_CR18","doi-asserted-by":"publisher","first-page":"461","DOI":"10.1007\/BF01585178","volume":"62","author":"D.B. Shmoys","year":"1993","unstructured":"Shmoys, D.B., Tardos, \u00c9.: An approximation algorithm for the generalized assignment problem. Math. Program.\u00a062, 461\u2013474 (1993)","journal-title":"Math. Program."},{"issue":"6","key":"19_CR19","doi-asserted-by":"publisher","first-page":"1012","DOI":"10.1145\/1217856.1217860","volume":"53","author":"D.B. 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\u00a053(6), 1012 (2006)","journal-title":"J. ACM"},{"issue":"1","key":"19_CR20","doi-asserted-by":"publisher","first-page":"46","DOI":"10.1145\/1122480.1122493","volume":"37","author":"C. Swamy","year":"2006","unstructured":"Swamy, C., Shmoys, D.B.: Approximation algorithms for 2-stage stochastic optimization problems. ACM SIGACT News\u00a037(1), 46 (2006)","journal-title":"ACM SIGACT News"}],"container-title":["Lecture Notes in Computer Science","Algorithms \u2013 ESA 2010"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-15781-3_19","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,6,3]],"date-time":"2023-06-03T02:58:36Z","timestamp":1685761116000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-15781-3_19"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010]]},"ISBN":["9783642157806","9783642157813"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-15781-3_19","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2010]]}}}