{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,16]],"date-time":"2026-03-16T10:14:40Z","timestamp":1773656080057,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":25,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540742074","type":"print"},{"value":"9783540742081","type":"electronic"}],"license":[{"start":{"date-parts":[[2007,1,1]],"date-time":"2007-01-01T00:00:00Z","timestamp":1167609600000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2007]]},"DOI":"10.1007\/978-3-540-74208-1_10","type":"book-chapter","created":{"date-parts":[[2007,8,27]],"date-time":"2007-08-27T14:52:26Z","timestamp":1188226346000},"page":"134-148","source":"Crossref","is-referenced-by-count":10,"title":["Stochastic Steiner Tree with Non-uniform Inflation"],"prefix":"10.1007","author":[{"given":"Anupam","family":"Gupta","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"MohammadTaghi","family":"Hajiaghayi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Amit","family":"Kumar","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"1","key":"10_CR1","doi-asserted-by":"publisher","first-page":"78","DOI":"10.1137\/S0097539792224474","volume":"24","author":"N. Alon","year":"1995","unstructured":"Alon, N., Karp, R.M., Peleg, D., West, D.: A graph-theoretic game and its application to the k-server problem. SIAM J. Comput.\u00a024(1), 78\u2013100 (1995)","journal-title":"SIAM J. Comput."},{"key":"10_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"257","DOI":"10.1007\/11538462_22","volume-title":"Approximation, Randomization and Combinatorial Optimization","author":"M. Charikar","year":"2005","unstructured":"Charikar, M., Chekuri, C., P\u00e1l, M.: Sampling bounds for stochastic optimization. In: Chekuri, C., Jansen, K., Rolim, J.D.P., Trevisan, L. (eds.) APPROX 2005 and RANDOM 2005. LNCS, vol.\u00a03624, pp. 257\u2013269. Springer, Heidelberg (2005)"},{"key":"10_CR3","doi-asserted-by":"crossref","first-page":"176","DOI":"10.1145\/1060590.1060617","volume-title":"STOC","author":"M. Charikar","year":"2005","unstructured":"Charikar, M., Karagiozova, A.: On non-uniform multicommodity buy-at-bulk network design. In: STOC, pp. 176\u2013182. ACM Press, New York (2005)"},{"key":"10_CR4","doi-asserted-by":"crossref","unstructured":"Chekuri, C., Hajiaghayi, M., Kortsarz, G., Salavatipour, M.R.: Approximation algorithms for non-uniform buy-at-bulk network design problems. In: FOCS (2006)","DOI":"10.1109\/FOCS.2006.15"},{"key":"10_CR5","unstructured":"Chekuri, C., Khanna, S., Naor, J.S.: A deterministic algorithm for the cost-distance problem. In: SODA, pp. 232\u2013233 (2001)"},{"key":"10_CR6","unstructured":"Chuzhoy, J., Gupta, A., Naor, J.S., Sinha, A.: On the approximability of network design problems. In: SODA, pp. 943\u2013951 (2005)"},{"key":"10_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"321","DOI":"10.1007\/11496915_24","volume-title":"Integer Programming and Combinatorial Optimization","author":"K. Dhamdhere","year":"2005","unstructured":"Dhamdhere, K., Ravi, R., Singh, M.: On two-stage stochastic minimum spanning trees. In: J\u00fcnger, M., Kaibel, V. (eds.) Integer Programming and Combinatorial Optimization. LNCS, vol.\u00a03509, pp. 321\u2013334. Springer, Heidelberg (2005)"},{"key":"10_CR8","doi-asserted-by":"crossref","first-page":"494","DOI":"10.1145\/1060590.1060665","volume-title":"STOC","author":"M. Elkin","year":"2005","unstructured":"Elkin, M., Emek, Y., Spielman, D.A., Teng, S.-H.: Lower-stretch spanning trees. In: STOC, pp. 494\u2013503. ACM Press, New York (2005)"},{"key":"10_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1051","DOI":"10.1007\/11523468_85","volume-title":"Automata, Languages and Programming","author":"A. Gupta","year":"2005","unstructured":"Gupta, A., P\u00e1l, M.: Stochastic Steiner trees without a root. In: Caires, L., Italiano, G.F., Monteiro, L., Palamidessi, C., Yung, M. (eds.) ICALP 2005. LNCS, vol.\u00a03580, pp. 1051\u20131063. Springer, Heidelberg (2005)"},{"key":"10_CR10","doi-asserted-by":"crossref","unstructured":"Gupta, A., P\u00e1l, M., Ravi, R., Sinha, A.: Boosted sampling: Approximation algorithms for stochastic optimization problems. In: STOC, pp. 417\u2013426 (2004)","DOI":"10.1145\/1007352.1007419"},{"key":"10_CR11","series-title":"Lecture Notes in Computer Science","first-page":"86","volume-title":"Approximation, Randomization and Combinatorial Optimization","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_CR12","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, pp. 218\u2013227 (2004)","DOI":"10.1109\/FOCS.2004.11"},{"key":"10_CR13","unstructured":"Hajiaghayi, M.T., Kortsarz, G., Salavatipour, M.R.: Approximating buy-at-bulk k-steiner trees. In: Electronic Colloquium on Computational Complexity (ECCC) (2006)"},{"key":"10_CR14","unstructured":"Hajiaghayi, M.T., Kortsarz, G., Salavatipour, M.R.: Polylogarithmic approximation algorithm for non-uniform multicommodity buy-at-bulk. In: Electronic Colloquium on Computational Complexity (ECCC) (2006)"},{"key":"10_CR15","unstructured":"Hayrapetyan, A., Swamy, C., Tardos, E.: Network design for information networks. In: SODA, pp. 933\u2013942 (2005)"},{"key":"10_CR16","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, pp. 684\u2013693 (2004)"},{"key":"10_CR17","doi-asserted-by":"publisher","first-page":"256","DOI":"10.1016\/S0022-0000(74)80044-9","volume":"9","author":"D.S. Johnson","year":"1974","unstructured":"Johnson, D.S.: Approximation algorithms for combinatorial problems. J. Comput. System Sci.\u00a09, 256\u2013278 (1974)","journal-title":"J. Comput. System Sci."},{"issue":"1","key":"10_CR18","doi-asserted-by":"publisher","first-page":"104","DOI":"10.1006\/jagm.1995.1029","volume":"19","author":"P. Klein","year":"1995","unstructured":"Klein, P., Ravi, R.: A nearly best-possible approximation algorithm for node-weighted Steiner trees. J. Algorithms\u00a019(1), 104\u2013115 (1995)","journal-title":"J. Algorithms"},{"key":"10_CR19","doi-asserted-by":"crossref","unstructured":"Meyerson, A.: Online algorithms for network design. In: SPAA, pp. 275\u2013280 (2004)","DOI":"10.1145\/1007912.1007958"},{"key":"10_CR20","doi-asserted-by":"crossref","unstructured":"Meyerson, A., Munagala, K., Plotkin, S.: Cost-distance: Two metric network design. In: FOCS, pp. 624\u2013630 (2000)","DOI":"10.1109\/SFCS.2000.892330"},{"key":"10_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1007\/11682462_4","volume-title":"LATIN 2006: Theoretical Informatics","author":"R. Ravi","year":"2006","unstructured":"Ravi, R.: Matching based augmentations for approximating connectivity problems. In: Correa, J.R., Hevia, A., Kiwi, M. (eds.) LATIN 2006. LNCS, vol.\u00a03887, pp. 13\u201324. Springer, Heidelberg (2006)"},{"key":"10_CR22","doi-asserted-by":"crossref","unstructured":"Ravi, R., Sinha, A.: Hedging uncertainty: Approximation algorithms for stochastic optimization problems. In: IPCO, pp. 101\u2013115 (2004)","DOI":"10.1007\/978-3-540-25960-2_8"},{"issue":"1","key":"10_CR23","doi-asserted-by":"publisher","first-page":"122","DOI":"10.1137\/S0895480101393155","volume":"19","author":"G. Robins","year":"2005","unstructured":"Robins, G., Zelikovsky, A.: Tighter bounds for graph Steiner tree approximation. SIAM J. Discrete Math.\u00a019(1), 122\u2013134 (2005)","journal-title":"SIAM J. Discrete Math."},{"key":"10_CR24","doi-asserted-by":"crossref","unstructured":"Shmoys, D., Swamy, C.: Stochastic optimization is (almost) as easy as deterministic optimization. In: FOCS, pp. 228\u2013237 (2004)","DOI":"10.1109\/FOCS.2004.62"},{"key":"10_CR25","doi-asserted-by":"crossref","unstructured":"Swamy, C., Shmoys, D.B.: Sampling-based approximation algorithms for multi-stage stochastic. In: FOCS, pp. 357\u2013366 (2005)","DOI":"10.1109\/SFCS.2005.67"}],"container-title":["Lecture Notes in Computer Science","Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-74208-1_10","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,20]],"date-time":"2025-01-20T17:37:29Z","timestamp":1737394649000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-74208-1_10"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007]]},"ISBN":["9783540742074","9783540742081"],"references-count":25,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-74208-1_10","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2007]]}}}