{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:36:36Z","timestamp":1759638996299,"version":"3.37.3"},"publisher-location":"Berlin, Heidelberg","reference-count":28,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642141645"},{"type":"electronic","value":"9783642141652"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2010]]},"DOI":"10.1007\/978-3-642-14165-2_42","type":"book-chapter","created":{"date-parts":[[2010,7,5]],"date-time":"2010-07-05T13:26:02Z","timestamp":1278336362000},"page":"490-502","source":"Crossref","is-referenced-by-count":17,"title":["Network Design via Core Detouring for Problems without a Core"],"prefix":"10.1007","author":[{"given":"Fabrizio","family":"Grandoni","sequence":"first","affiliation":[]},{"given":"Thomas","family":"Rothvo\u00df","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"42_CR1","doi-asserted-by":"crossref","unstructured":"Becchetti, L., K\u00f6nemann, J., Leonardi, S., P\u00e1l, M.: Sharing the cost more efficiently: improved approximation for multicommodity rent-or-buy. ACM Transactions on Algorithms\u00a03(2) (2007)","DOI":"10.1145\/1240233.1240246"},{"key":"42_CR2","unstructured":"Byrka, J., Grandoni, F., Rothvo\u00df, T., Sanit\u00e0, L.: An Improved LP-based Approximation for Steiner tree. In: STOC (to appear, 2010) (Best Paper Award)"},{"key":"42_CR3","doi-asserted-by":"crossref","unstructured":"Duffield, N.G., Goyal, P., Greenberg, A., Mishra, P., Ramakrishnan, K.K., van der Merwe, J.E.: A flexible model for resource management in virtual private networks. In: SIGCOMM, pp. 95\u2013108 (1999)","DOI":"10.1145\/316188.316209"},{"key":"42_CR4","doi-asserted-by":"crossref","unstructured":"Eisenbrand, F., Grandoni, F.: An improved approximation algorithm for virtual private network design. In: SODA, pp. 928\u2013932 (2005)","DOI":"10.1007\/11523468_93"},{"issue":"3","key":"42_CR5","doi-asserted-by":"publisher","first-page":"706","DOI":"10.1137\/060654827","volume":"37","author":"F. Eisenbrand","year":"2007","unstructured":"Eisenbrand, F., Grandoni, F., Oriolo, G., Skutella, M.: New approaches for virtual private network design. SIAM Journal on Computing\u00a037(3), 706\u2013721 (2007)","journal-title":"SIAM Journal on Computing"},{"key":"42_CR6","unstructured":"Eisenbrand, F., Grandoni, F., Rothvo\u00df, T., Sch\u00e4fer, G.: Approximating connected facility location problems via random facility sampling and core detouring. In: SODA, pp. 1174\u20131183 (2008)"},{"issue":"2","key":"42_CR7","doi-asserted-by":"publisher","first-page":"287","DOI":"10.1006\/jagm.1997.0866","volume":"24","author":"J.A. Fingerhut","year":"1997","unstructured":"Fingerhut, J.A., Suri, S., Turner, J.S.: Designing least-cost nonblocking broadband networks. Journal of Algorithms\u00a024(2), 287\u2013309 (1997)","journal-title":"Journal of Algorithms"},{"key":"42_CR8","doi-asserted-by":"crossref","unstructured":"Fleischer, L., K\u00f6nemann, J., Leonardi, S., Sch\u00e4fer, G.: Simple cost sharing schemes for multicommodity rent-or-buy and stochastic steiner tree. In: STOC, pp. 663\u2013670 (2006)","DOI":"10.1145\/1132516.1132609"},{"key":"42_CR9","unstructured":"Garg, N., Gupta, A., Leonardi, S., Sankowski, P.: Stochastic analyses for online combinatorial optimization problems. In: SODA, pp. 942\u2013951 (2008)"},{"key":"42_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"170","DOI":"10.1007\/3-540-45535-3_14","volume-title":"Integer Programming and Combinatorial Optimization","author":"N. Garg","year":"2001","unstructured":"Garg, N., Khandekar, R., Konjevod, G., Ravi, R., Salman, F., Sinha, A.: On the integrality gap of a natural formulation of the single-sink buy-at-bulk network design problem. In: Aardal, K., Gerards, B. (eds.) IPCO 2001. LNCS, vol.\u00a02081, pp. 170\u2013184. Springer, Heidelberg (2001)"},{"key":"42_CR11","doi-asserted-by":"crossref","unstructured":"Goyal, N., Olver, N., Shepherd, F.B.: The VPN conjecture is true. In: STOC, pp. 443\u2013450 (2008)","DOI":"10.1145\/1374376.1374440"},{"key":"42_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1007\/11940128_13","volume-title":"Algorithms and Computation","author":"F. Grandoni","year":"2006","unstructured":"Grandoni, F., Italiano, G.F.: Improved approximation for single-sink buy-at-bulk. In: Asano, T. (ed.) ISAAC 2006. LNCS, vol.\u00a04288, pp. 111\u2013120. Springer, Heidelberg (2006)"},{"issue":"3","key":"42_CR13","doi-asserted-by":"publisher","first-page":"361","DOI":"10.1016\/j.orl.2007.10.008","volume":"36","author":"F. Grandoni","year":"2008","unstructured":"Grandoni, F., Kaibel, V., Oriolo, G., Skutella, M.: A short proof of the VPN Tree Routing Conjecture on ring networks. Operations Research Letters\u00a036(3), 361\u2013365 (2008)","journal-title":"Operations Research Letters"},{"issue":"6","key":"42_CR14","doi-asserted-by":"publisher","first-page":"2426","DOI":"10.1137\/050643635","volume":"38","author":"S. Guha","year":"2009","unstructured":"Guha, S., Meyerson, A., Munagala, K.: A constant factor approximation for the single sink edge installation problem. SIAM Journal on Computing\u00a038(6), 2426\u20132442 (2009)","journal-title":"SIAM Journal on Computing"},{"key":"42_CR15","doi-asserted-by":"crossref","unstructured":"Gupta, A., Kleinberg, J., Kumar, A., Rastogi, R., Yener, B.: Provisioning a virtual private network: a network design problem for multicommodity flow. In: STOC, pp. 389\u2013398 (2001)","DOI":"10.1145\/380752.380830"},{"issue":"3","key":"42_CR16","doi-asserted-by":"publisher","first-page":"11","DOI":"10.1145\/1236457.1236458","volume":"54","author":"A. Gupta","year":"2007","unstructured":"Gupta, A., Kumar, A., Pal, M., Roughgarden, T.: Approximation via cost-sharing: simpler and better approximation algorithms for network design. Journal of the ACM\u00a054(3), 11 (2007)","journal-title":"Journal of the ACM"},{"key":"42_CR17","doi-asserted-by":"crossref","unstructured":"Gupta, A., Kumar, A., Roughgarden, T.: Simpler and better approximation algorithms for network design. In: STOC, pp. 365\u2013372 (2003)","DOI":"10.1145\/780542.780597"},{"key":"42_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","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)"},{"issue":"2","key":"42_CR19","doi-asserted-by":"publisher","first-page":"482","DOI":"10.1137\/050626259","volume":"21","author":"C.A.J. Hurkens","year":"2007","unstructured":"Hurkens, C.A.J., Keijsper, J.C.M., Stougie, L.: Virtual Private Network Design: A Proof of the Tree Routing Conjecture on Ring Networks. SIAM Journal on Discrete Mathematics\u00a021(2), 482\u2013503 (2007)","journal-title":"SIAM Journal on Discrete Mathematics"},{"issue":"6","key":"42_CR20","doi-asserted-by":"publisher","first-page":"601","DOI":"10.1016\/j.orl.2005.09.005","volume":"34","author":"G.F. Italiano","year":"2006","unstructured":"Italiano, G.F., Leonardi, S., Oriolo, G.: Design of trees in the hose model: The balanced case. Operations Research Letters\u00a034(6), 601\u2013606 (2006)","journal-title":"Operations Research Letters"},{"key":"42_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"336","DOI":"10.1007\/978-3-540-27810-8_29","volume-title":"Algorithm Theory - SWAT 2004","author":"R. Jothi","year":"2004","unstructured":"Jothi, R., Raghavachari, B.: Improved approximation algorithms for the single-sink buy-at-bulk network design problems. In: Hagerup, T., Katajainen, J. (eds.) SWAT 2004. LNCS, vol.\u00a03111, pp. 336\u2013348. Springer, Heidelberg (2004)"},{"key":"42_CR22","doi-asserted-by":"crossref","unstructured":"Karger, D.R., Minkoff, M.: Building steiner trees with incomplete global knowledge. In: FOCS, pp. 613\u2013623 (2000)","DOI":"10.1109\/SFCS.2000.892329"},{"key":"42_CR23","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":"42_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"326","DOI":"10.1007\/978-3-642-03685-9_25","volume-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques","author":"T. Rothvo\u00df","year":"2009","unstructured":"Rothvo\u00df, T., Sanit\u00e0, L.: On the complexity of the asymmetric VPN problem. In: Dinur, I., Jansen, K., Naor, J., Rolim, J. (eds.) Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques. LNCS, vol.\u00a05687, pp. 326\u2013338. Springer, Heidelberg (2009)"},{"key":"42_CR25","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"256","DOI":"10.1007\/3-540-45753-4_22","volume-title":"Approximation Algorithms for Combinatorial Optimization","author":"C. Swamy","year":"2002","unstructured":"Swamy, C., Kumar, A.: Primal\u2013dual algorithms for connected facility location problems. In: Jansen, K., Leonardi, S., Vazirani, V.V. (eds.) APPROX 2002. LNCS, vol.\u00a02462, pp. 256\u2013269. Springer, Heidelberg (2002)"},{"key":"42_CR26","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"331","DOI":"10.1007\/978-3-540-68891-4_23","volume-title":"Integer Programming and Combinatorial Optimization","author":"D.B. Shmoys","year":"2008","unstructured":"Shmoys, D.B., Talwar, K.: A Constant Approximation Algorithm for the a priori Traveling Salesman Problem. In: Lodi, A., Panconesi, A., Rinaldi, G. (eds.) IPCO 2008. LNCS, vol.\u00a05035, pp. 331\u2013343. Springer, Heidelberg (2008)"},{"key":"42_CR27","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"475","DOI":"10.1007\/3-540-47867-1_33","volume-title":"Integer Programming and Combinatorial Optimization","author":"K. Talwar","year":"2002","unstructured":"Talwar, K.: The single-sink buy-at-bulk LP has constant integrality gap. In: Cook, W.J., Schulz, A.S. (eds.) IPCO 2002. LNCS, vol.\u00a02337, pp. 475\u2013486. Springer, Heidelberg (2002)"},{"key":"42_CR28","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"830","DOI":"10.1007\/978-3-540-87744-8_69","volume-title":"Algorithms - ESA 2008","author":"A. Zuylen van","year":"2008","unstructured":"van Zuylen, A.: Deterministic Sampling Algorithms for Network Design. In: Halperin, D., Mehlhorn, K. (eds.) ESA 2008. LNCS, vol.\u00a05193, pp. 830\u2013841. Springer, Heidelberg (2008)"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-14165-2_42.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,22]],"date-time":"2025-02-22T16:31:13Z","timestamp":1740241873000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-14165-2_42"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010]]},"ISBN":["9783642141645","9783642141652"],"references-count":28,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-14165-2_42","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2010]]}}}