{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,1,10]],"date-time":"2025-01-10T16:10:11Z","timestamp":1736525411476,"version":"3.32.0"},"publisher-location":"Berlin, Heidelberg","reference-count":19,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540380443"},{"type":"electronic","value":"9783540380450"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2006]]},"DOI":"10.1007\/11830924_10","type":"book-chapter","created":{"date-parts":[[2006,8,25]],"date-time":"2006-08-25T12:33:54Z","timestamp":1156509234000},"page":"82-94","source":"Crossref","is-referenced-by-count":3,"title":["Single-Source Stochastic Routing"],"prefix":"10.1007","author":[{"given":"Shuchi","family":"Chawla","sequence":"first","affiliation":[]},{"given":"Tim","family":"Roughgarden","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"10_CR1","series-title":"Springer Series in Operations Research","volume-title":"Introduction to stochastic programming","author":"J.R. Birge","year":"1997","unstructured":"Birge, J.R., Louveaux, F.: Introduction to stochastic programming. Springer Series in Operations Research. Springer, New York (1997)"},{"key":"10_CR2","unstructured":"Chawla, S., Roughgarden, T.: Single-source stochastic routing, http:\/\/www.cs.cmu.edu\/~shuchi\/papers\/stoch-routing.ps"},{"key":"10_CR3","doi-asserted-by":"publisher","first-page":"197","DOI":"10.1287\/mnsc.1.3-4.197","volume":"1","author":"G.B. Dantzig","year":"1955","unstructured":"Dantzig, G.B.: Linear programming under uncertainty. Management Science\u00a01, 197\u2013206 (1955)","journal-title":"Management Science"},{"key":"10_CR4","unstructured":"Dean, B., Goemans, M., Vondrak, J.: Adaptivity and approximation for stochastic packing problems. In: SODA 2005, pp. 395\u2013404 (2005)"},{"key":"10_CR5","doi-asserted-by":"crossref","unstructured":"Dean, B., Goemans, M., Vondrak, J.: The benefit of adaptivity: Approximating the stochastic knapsack problem. In: FOCS 2004, pp. 208\u2013217 (2004)","DOI":"10.1109\/FOCS.2004.15"},{"key":"10_CR6","unstructured":"Dean, B.: Approximation Algorithms for Stochastic Scheduling Problems. Ph.D thesis, Massachusetts Institute of Technology, Massachusetts (2005)"},{"issue":"1","key":"10_CR7","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1007\/s004930050043","volume":"19","author":"Y. Dinitz","year":"1999","unstructured":"Dinitz, Y., Garg, N., Goemans, M.X.: On the single-source unsplittable flow problem. Combinatorica\u00a019(1), 17\u201342 (1999)","journal-title":"Combinatorica"},{"key":"10_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"532","DOI":"10.1007\/11682462_50","volume-title":"LATIN 2006: Theoretical Informatics","author":"M. Goemans","year":"2006","unstructured":"Goemans, M., Vondrak, J.: Stochastic covering and adaptivity. In: Correa, J.R., Hevia, A., Kiwi, M. (eds.) LATIN 2006. LNCS, vol.\u00a03887, pp. 532\u2013543. Springer, Heidelberg (2006)"},{"key":"10_CR9","doi-asserted-by":"crossref","unstructured":"Gupta, A., Pal, M., Ravi, R., Sinha, A.: Boosted sampling: Approximation algorithms for stochastic optimization. In: STOC 2004, pp. 417\u2013426 (2004)","DOI":"10.1145\/1007352.1007419"},{"key":"10_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"86","DOI":"10.1007\/11538462_8","volume-title":"Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques","author":"A. Gupta","year":"2005","unstructured":"Gupta, A., P\u00e1l, M., Ravi, R., Sinha, A.: What about wednesday? Approximation algorithms for multistage stochastic optimization. In: Chekuri, C., Jansen, K., Rolim, J.D.P., Trevisan, L. (eds.) APPROX 2005 and RANDOM 2005. LNCS, vol.\u00a03624, pp. 86\u201398. Springer, Heidelberg (2005)"},{"key":"10_CR11","doi-asserted-by":"crossref","unstructured":"Gupta, A., Ravi, R., Sinha, A.: An edge in time saves nine: Lp rounding approximation algorithms for stochastic network design. In: FOCS 2004, pp. 218\u2013227 (2004)","DOI":"10.1109\/FOCS.2004.11"},{"key":"10_CR12","unstructured":"Immorlica, N., Karger, D., Minkoff, M., Mirrokni, V.: On the costs and benefits of procrastination: Approximation algorithms for stochastic combinatorial optimization problems. In: SODA 2004, pp. 684\u2013693 (2004)"},{"key":"10_CR13","doi-asserted-by":"crossref","unstructured":"Kleinberg, J.: Single-source unsplittable flow. In: FOCS 1996, pp. 68\u201377 (1996)","DOI":"10.1109\/SFCS.1996.548465"},{"issue":"3","key":"10_CR14","doi-asserted-by":"publisher","first-page":"919","DOI":"10.1137\/S0097539799355314","volume":"31","author":"S.G. Kolliopoulos","year":"2001","unstructured":"Kolliopoulos, S.G., Stein, C.: Approximation algorithms for single-source unsplittable flow. SIAM Journal on Computing\u00a031(3), 919\u2013946 (2001)","journal-title":"SIAM Journal on Computing"},{"key":"10_CR15","doi-asserted-by":"crossref","unstructured":"Ravi, R., Sinha, A.: Hedging uncertainty: approximation algorithms for stochastic optimization problems. Mathematical Programming (2005)","DOI":"10.1007\/978-3-540-25960-2_8"},{"key":"10_CR16","unstructured":"Shmoys, D., Swamy, C.: Sampling-based approximation algorithms for multi-stage stochastic optimization. In: FOCS 2005 (2005)"},{"key":"10_CR17","doi-asserted-by":"crossref","unstructured":"Shmoys, D., Swamy, C.: Stochastic optimization is (almost) as easy as deterministic optimization. In: FOCS 2004, pp. 228\u2013237 (2004)","DOI":"10.1109\/FOCS.2004.62"},{"key":"10_CR18","unstructured":"Stochastic programming community homepage, http:\/\/stoprog.org\/"},{"issue":"13","key":"10_CR19","doi-asserted-by":"publisher","first-page":"743","DOI":"10.1112\/plms\/s3-13.1.743","volume":"3","author":"W.T. Tutte","year":"1963","unstructured":"Tutte, W.T.: How to draw a graph. Proceedings of the London Mathematical Society\u00a03(13), 743\u2013768 (1963)","journal-title":"Proceedings of the London Mathematical Society"}],"container-title":["Lecture Notes in Computer Science","Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11830924_10.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,10]],"date-time":"2025-01-10T15:29:44Z","timestamp":1736522984000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11830924_10"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006]]},"ISBN":["9783540380443","9783540380450"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/11830924_10","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2006]]}}}