{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,3]],"date-time":"2025-05-03T04:13:06Z","timestamp":1746245586883,"version":"3.40.4"},"publisher-location":"Cham","reference-count":19,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319075563"},{"type":"electronic","value":"9783319075570"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014]]},"DOI":"10.1007\/978-3-319-07557-0_10","type":"book-chapter","created":{"date-parts":[[2014,5,17]],"date-time":"2014-05-17T11:50:30Z","timestamp":1400327430000},"page":"114-125","source":"Crossref","is-referenced-by-count":5,"title":["On the Adaptivity Gap of Stochastic Orienteering"],"prefix":"10.1007","author":[{"given":"Nikhil","family":"Bansal","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Viswanath","family":"Nagarajan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"10_CR1","doi-asserted-by":"crossref","unstructured":"Bansal, N., Blum, A., Chawla, S., Meyerson, A.: Approximation algorithms for deadline-TSP and vehicle routing with time-windows. In: STOC, pp. 166\u2013174 (2004)","DOI":"10.1145\/1007352.1007385"},{"issue":"4","key":"10_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(4), 733\u2013762 (2012)","journal-title":"Algorithmica"},{"key":"10_CR3","unstructured":"Bansal, N., Nagarajan, V.: On the adaptivity gap of stochastic orienteering. CoRR, abs\/1311.3623 (2013)"},{"key":"10_CR4","doi-asserted-by":"crossref","unstructured":"Bhalgat, A.: A (2\u2009+\u2009\u03b5)-approximation algorithm for the stochastic knapsack problem (2011) (unpublished manuscript)","DOI":"10.1137\/1.9781611973082.127"},{"key":"10_CR5","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"},{"issue":"2","key":"10_CR6","doi-asserted-by":"publisher","first-page":"653","DOI":"10.1137\/050645464","volume":"37","author":"A. Blum","year":"2007","unstructured":"Blum, A., Chawla, S., Karger, D.R., Lane, T., Meyerson, A., Minkoff, M.: Approximation algorithms for orienteering and discounted-reward TSP. SIAM J. Comput.\u00a037(2), 653\u2013670 (2007)","journal-title":"SIAM J. Comput."},{"key":"10_CR7","doi-asserted-by":"crossref","unstructured":"Chekuri, C., Korula, N., P\u00e1l, M.: Improved algorithms for orienteering and related problems. ACM TALG\u00a08(3) (2012)","DOI":"10.1145\/2229163.2229167"},{"key":"10_CR8","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)"},{"issue":"4","key":"10_CR9","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)","journal-title":"Math. Oper. Res."},{"issue":"2","key":"10_CR10","doi-asserted-by":"publisher","first-page":"630","DOI":"10.1137\/S0097539704446232","volume":"37","author":"N. Garg","year":"2007","unstructured":"Garg, N., K\u00f6nemann, J.: Faster and simpler algorithms for multicommodity flow and other fractional packing problems. SIAM J. Comput.\u00a037(2), 630\u2013652 (2007)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"10_CR11","doi-asserted-by":"publisher","first-page":"307","DOI":"10.1002\/1520-6750(198706)34:3<307::AID-NAV3220340302>3.0.CO;2-D","volume":"34","author":"B.L. Golden","year":"1987","unstructured":"Golden, B.L., Levy, L., Vohra, R.: The orienteering problem. Naval Research Logistics\u00a034(3), 307\u2013318 (1987)","journal-title":"Naval Research Logistics"},{"key":"10_CR12","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, Part II. LNCS, vol.\u00a05556, pp. 496\u2013507. Springer, Heidelberg (2009)"},{"key":"10_CR13","doi-asserted-by":"crossref","unstructured":"Gupta, A., Krishnaswamy, R., Molinaro, M., Ravi, R.: Approximation algorithms for correlated knapsacks and non-martingale bandits. In: FOCS, pp. 827\u2013836 (2011)","DOI":"10.1109\/FOCS.2011.48"},{"key":"10_CR14","doi-asserted-by":"crossref","unstructured":"Gupta, A., Krishnaswamy, R., Nagarajan, V., Ravi, R.: Approximation algorithms for stochastic orienteering. In: SODA, pp. 1522\u20131538 (2012)","DOI":"10.1137\/1.9781611973099.121"},{"key":"10_CR15","doi-asserted-by":"crossref","unstructured":"Ma, W.: Improvements and generalizations of stochastic knapsack and multi-armed bandit approximation algorithms: Extended abstract. In: SODA, pp. 1154\u20131163 (2014)","DOI":"10.1137\/1.9781611973402.85"},{"key":"10_CR16","doi-asserted-by":"crossref","unstructured":"Plotkin, S.A., Shmoys, D.B., Tardos, E.: Fast approximation algorithms for fractional packing and covering problems. In: FOCS, pp. 495\u2013504 (1991)","DOI":"10.1109\/SFCS.1991.185411"},{"issue":"1","key":"10_CR17","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.ejor.2010.03.045","volume":"209","author":"P. Vansteenwegena","year":"2011","unstructured":"Vansteenwegena, P., Souffriaua, W., Oudheusdena, D.V.: The orienteering problem: A survey. Eur.\u00a0J.\u00a0Oper.\u00a0Res.\u00a0209(1), 1\u201310 (2011)","journal-title":"Eur.\u00a0J.\u00a0Oper.\u00a0Res."},{"key":"10_CR18","unstructured":"Weyland, D.: Stochastic Vehicle Routing - From Theory to Practice. PhD thesis, University of Lugano, Switzerland (2013)"},{"key":"10_CR19","doi-asserted-by":"crossref","unstructured":"Zhang, T.: Data dependent concentration bounds for sequential prediction algorithms. In: COLT, pp. 173\u2013187 (2005)","DOI":"10.1007\/11503415_12"}],"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-319-07557-0_10","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,2]],"date-time":"2025-05-02T23:25:30Z","timestamp":1746228330000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-07557-0_10"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014]]},"ISBN":["9783319075563","9783319075570"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-07557-0_10","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2014]]}}}