{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,10]],"date-time":"2026-01-10T22:22:29Z","timestamp":1768083749384,"version":"3.49.0"},"publisher-location":"Berlin, Heidelberg","reference-count":23,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642366932","type":"print"},{"value":"9783642366949","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-3-642-36694-9_18","type":"book-chapter","created":{"date-parts":[[2013,3,11]],"date-time":"2013-03-11T10:08:39Z","timestamp":1362996519000},"page":"205-216","source":"Crossref","is-referenced-by-count":39,"title":["A Stochastic Probing Problem with Applications"],"prefix":"10.1007","author":[{"given":"Anupam","family":"Gupta","sequence":"first","affiliation":[]},{"given":"Viswanath","family":"Nagarajan","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"18_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"266","DOI":"10.1007\/978-3-642-02927-1_23","volume-title":"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: Albers, S., Marchetti-Spaccamela, A., Matias, Y., Nikoletseas, S., Thomas, W. (eds.) ICALP 2009, Part I. LNCS, vol.\u00a05555, pp. 266\u2013278. Springer, Heidelberg (2009)"},{"key":"18_CR2","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\u00a063, 733\u2013762 (2012)","journal-title":"Algorithmica"},{"key":"18_CR3","doi-asserted-by":"crossref","unstructured":"Chawla, S., Hartline, J.D., Malec, D.L., Sivan, B.: Multi-parameter mechanism design and sequential posted pricing. In: STOC, pp. 311\u2013320 (2010)","DOI":"10.1145\/1807406.1807428"},{"key":"18_CR4","doi-asserted-by":"crossref","unstructured":"Yan, Q.: Mechanism Design via Correlation Gap. In: SODA, pp. 710\u2013719 (2011)","DOI":"10.1137\/1.9781611973082.56"},{"key":"18_CR5","doi-asserted-by":"crossref","unstructured":"Kleinberg, R., Weinberg, S.M.: Matroid prophet inequalities. In: STOC, pp. 123\u2013136 (2012)","DOI":"10.1145\/2213977.2213991"},{"key":"18_CR6","doi-asserted-by":"publisher","first-page":"924","DOI":"10.1145\/331524.331530","volume":"46","author":"R.H. M\u00f6hring","year":"1999","unstructured":"M\u00f6hring, R.H., Schulz, A.S., Uetz, M.: Approximation in stochastic scheduling: the power of LP-based priority policies. Journal of the ACM (JACM)\u00a046, 924\u2013942 (1999)","journal-title":"Journal of the ACM (JACM)"},{"key":"18_CR7","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, 945\u2013964 (2008)","journal-title":"Math. Oper. Res."},{"key":"18_CR8","unstructured":"Dean, B.C., Goemans, M.X., Vondr\u00e1k, J.: Adaptivity and approximation for stochastic packing problems. In: SODA, pp. 395\u2013404 (2005)"},{"key":"18_CR9","doi-asserted-by":"crossref","unstructured":"Guha, S., Munagala, K.: Approximation algorithms for budgeted learning problems. In: STOC, pp. 104\u2013113 (2007)","DOI":"10.1145\/1250790.1250807"},{"key":"18_CR10","doi-asserted-by":"publisher","first-page":"731","DOI":"10.1016\/j.ipl.2011.05.007","volume":"111","author":"M. Adamczyk","year":"2011","unstructured":"Adamczyk, M.: Improved analysis of the greedy algorithm for stochastic matching. Inf. Process. Lett.\u00a0111, 731\u2013737 (2011)","journal-title":"Inf. Process. Lett."},{"key":"18_CR11","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1007\/BFb0121195","volume":"8","author":"M. Fisher","year":"1978","unstructured":"Fisher, M., Nemhauser, G., Wolsey, L.: An analysis of approximations for maximizing submodular set functions II. Mathematical Programming Study\u00a08, 73\u201387 (1978)","journal-title":"Mathematical Programming Study"},{"key":"18_CR12","unstructured":"Jenkyns, T.: The efficiency of the \u201cgreedy\u201d algorithm. In: 7th South Eastern Conference on Combinatorics, Graph Theory and Computing, pp. 341\u2013350 (1976)"},{"key":"18_CR13","unstructured":"Chekuri, C., Vondr\u00e1k, J., Zenklusen, R.: Submodular function maximization via the multilinear relaxation and contention resolution schemes. In: STOC, pp. 783\u2013792 (2011), Full version \n                  \n                    http:\/\/arxiv.org\/abs\/1105.4593"},{"key":"18_CR14","doi-asserted-by":"crossref","unstructured":"Sandholm, T., Gilpin, A.: Sequences of take-it-or-leave-it offers: near-optimal auctions without full valuation revelation. In: 5th International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS, pp. 1127\u20131134 (2006)","DOI":"10.1145\/1160633.1160839"},{"key":"18_CR15","doi-asserted-by":"crossref","unstructured":"Blumrosen, L., Holenstein, T.: Posted prices vs. negotiations: an asymptotic analysis. In: ACM Conference on Electronic Commerce (2008)","DOI":"10.1145\/1386790.1386801"},{"key":"18_CR16","doi-asserted-by":"publisher","first-page":"58","DOI":"10.1287\/moor.6.1.58","volume":"6","author":"R. Myerson","year":"1981","unstructured":"Myerson, R.: Optimal auction design. Mathematics of Operations Research\u00a06, 58\u201373 (1981)","journal-title":"Mathematics of Operations Research"},{"key":"18_CR17","doi-asserted-by":"crossref","unstructured":"Bhalgat, A., Goel, A., Khanna, S.: Improved approximation results for stochastic knapsack problems. In: SODA, pp. 1647\u20131665 (2011)","DOI":"10.1137\/1.9781611973082.127"},{"key":"18_CR18","doi-asserted-by":"crossref","unstructured":"Bhalgat, A.: A (2\u2009+\u2009\u03b5)-approximation algorithm for the stochastic knapsack problem (2011) (manuscript)","DOI":"10.1137\/1.9781611973082.127"},{"key":"18_CR19","unstructured":"Vohra, R.: Mechanism Design: A Linear Programming Approach. Cambridge University Press (2011)"},{"key":"18_CR20","doi-asserted-by":"crossref","unstructured":"Bhattacharya, S., Goel, G., Gollapudi, S., Munagala, K.: Budget constrained auctions with heterogeneous items. In: STOC, pp. 379\u2013388 (2010)","DOI":"10.1145\/1806689.1806743"},{"key":"18_CR21","unstructured":"Schrijver, A.: Combinatorial Optimization. Springer (2003)"},{"key":"18_CR22","doi-asserted-by":"crossref","unstructured":"Chekuri, C., Mydlarz, M., Shepherd, F.B.: Multicommodity demand flow in a tree and packing integer programs. ACM Transactions on Algorithms 3 (2007)","DOI":"10.1145\/1273340.1273343"},{"key":"18_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"369","DOI":"10.1007\/978-3-642-13036-6_28","volume-title":"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: Eisenbrand, F., Shepherd, F.B. (eds.) IPCO 2010. LNCS, vol.\u00a06080, pp. 369\u2013382. Springer, Heidelberg (2010)"}],"container-title":["Lecture Notes in Computer Science","Integer Programming and Combinatorial Optimization"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-36694-9_18","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,11]],"date-time":"2019-05-11T17:33:55Z","timestamp":1557596035000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-36694-9_18"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783642366932","9783642366949"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-36694-9_18","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013]]}}}