{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:21:23Z","timestamp":1759638083873,"version":"3.38.0"},"publisher-location":"Berlin, Heidelberg","reference-count":30,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642208065"},{"type":"electronic","value":"9783642208072"}],"license":[{"start":{"date-parts":[[2011,1,1]],"date-time":"2011-01-01T00:00:00Z","timestamp":1293840000000},"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":[[2011]]},"DOI":"10.1007\/978-3-642-20807-2_20","type":"book-chapter","created":{"date-parts":[[2011,6,18]],"date-time":"2011-06-18T13:58:49Z","timestamp":1308405529000},"page":"248-260","source":"Crossref","is-referenced-by-count":11,"title":["Approximation Algorithms for Single and Multi-Commodity Connected Facility Location"],"prefix":"10.1007","author":[{"given":"Fabrizio","family":"Grandoni","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Thomas","family":"Rothvo\u00df","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"20_CR1","doi-asserted-by":"publisher","first-page":"440","DOI":"10.1137\/S0097539792236237","volume":"24","author":"A. Agrawal","year":"1995","unstructured":"Agrawal, A., Klein, P., Ravi, R.: When trees collide: an approximation algorithm for the generalized Steiner problem on networks. SIAM Journal on Computing\u00a024, 440\u2013456 (1995)","journal-title":"SIAM Journal on Computing"},{"key":"20_CR2","doi-asserted-by":"crossref","unstructured":"Awerbuch, B., Azar, Y.: Buy-at-bulk network design. In: FOCS, pp. 542\u2013547 (1997)","DOI":"10.1109\/SFCS.1997.646143"},{"key":"20_CR3","unstructured":"Becchetti, L., K\u00f6nemann, J., Leonardi, S., P\u00e1l, M.: Sharing the cost more efficiently: improved approximation for multicommodity rent-or-buy. In: SODA, pp. 375\u2013384 (2005)"},{"key":"20_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"29","DOI":"10.1007\/978-3-540-74208-1_3","volume-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques","author":"J. Byrka","year":"2007","unstructured":"Byrka, J.: An optimal bifactor approximation algorithm for the metric uncapacitated facility location problem. In: Charikar, M., Jansen, K., Reingold, O., Rolim, J.D.P. (eds.) RANDOM 2007 and APPROX 2007. LNCS, vol.\u00a04627, pp. 29\u201343. Springer, Heidelberg (2007)"},{"key":"20_CR5","doi-asserted-by":"crossref","unstructured":"Byrka, J., Grandoni, F., Rothvo\u00df, T., Sanit\u00e0, L.: An improved LP-based approximation for Steiner tree. In: STOC, pp. 583\u2013592 (2010)","DOI":"10.1145\/1806689.1806769"},{"issue":"3","key":"20_CR6","doi-asserted-by":"publisher","first-page":"207","DOI":"10.1016\/j.tcs.2008.06.046","volume":"406","author":"M. Chleb\u00edk","year":"2008","unstructured":"Chleb\u00edk, M., Chleb\u00edkov\u00e1, J.: The Steiner tree problem on graphs: Inapproximability results. Theoretical Computer Science\u00a0406(3), 207\u2013214 (2008)","journal-title":"Theoretical Computer Science"},{"key":"20_CR7","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":"20_CR8","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":"20_CR9","doi-asserted-by":"publisher","first-page":"709","DOI":"10.1016\/j.jcss.2010.02.001","volume":"76","author":"F. Eisenbrand","year":"2010","unstructured":"Eisenbrand, F., Grandoni, F., Rothvo\u00df, T., Sch\u00e4fer, G.: Connected facility location via random facility sampling and core detouring. Journal of Computer and System Sciences\u00a076, 709\u2013726 (2010)","journal-title":"Journal of Computer and System Sciences"},{"key":"20_CR10","doi-asserted-by":"crossref","unstructured":"Feige, U.: A Threshold of ln n for Approximating Set Cover. Journal of the ACM\u00a045(4) (1998)","DOI":"10.1145\/285055.285059"},{"issue":"3","key":"20_CR11","doi-asserted-by":"publisher","first-page":"485","DOI":"10.1016\/j.jcss.2004.04.011","volume":"69","author":"J. Fakcharoenphol","year":"2004","unstructured":"Fakcharoenphol, J., Rao, S., Talwar, K.: A tight bound on approximating arbitrary metrics by tree metrics. Journal of Computer and System Sciences\u00a069(3), 485\u2013497 (2004)","journal-title":"Journal of Computer and System Sciences"},{"key":"20_CR12","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":"20_CR13","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":"20_CR14","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)"},{"key":"20_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"490","DOI":"10.1007\/978-3-642-14165-2_42","volume-title":"Automata, Languages and Programming","author":"F. Grandoni","year":"2010","unstructured":"Grandoni, F., Rothvo\u00df, T.: Network design via core detouring for problems without a core. In: Abramsky, S., Gavoille, C., Kirchner, C., Meyer auf der Heide, F., Spirakis, P.G. (eds.) ICALP 2010. LNCS, vol.\u00a06198, pp. 490\u2013502. Springer, Heidelberg (2010)"},{"issue":"1","key":"20_CR16","doi-asserted-by":"publisher","first-page":"228","DOI":"10.1006\/jagm.1998.0993","volume":"31","author":"S. Guha","year":"1999","unstructured":"Guha, S., Khuller, S.: Greedy Strikes Back: Improved Facility Location Algorithms. Journal of Algorithms\u00a031(1), 228\u2013248 (1999)","journal-title":"Journal of Algorithms"},{"issue":"6","key":"20_CR17","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":"20_CR18","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"},{"key":"20_CR19","doi-asserted-by":"crossref","unstructured":"Gupta, A., Kumar, A.: A constant-factor approximation for stochastic Steiner forest. In: STOC, pp. 659\u2013668 (2009)","DOI":"10.1145\/1536414.1536504"},{"issue":"3","key":"20_CR20","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":"20_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"139","DOI":"10.1007\/978-3-540-27821-4_13","volume-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques","author":"A. Gupta","year":"2004","unstructured":"Gupta, A., Srinivasan, A., Tardos, \u00c9.: Cost-sharing mechanisms for network design. In: Jansen, K., Khanna, S., Rolim, J.D.P., Ron, D. (eds.) RANDOM 2004 and APPROX 2004. LNCS, vol.\u00a03122, pp. 139\u2013150. Springer, Heidelberg (2004)"},{"key":"20_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","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":"20_CR23","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":"20_CR24","doi-asserted-by":"crossref","unstructured":"Kumar, A., Gupta, A., Roughgarden, T.: A constant-factor approximation algorithm for the multicommodity rent-or-buy problem. In: FOCS, pp. 333\u2013342 (2002)","DOI":"10.1109\/SFCS.2002.1181956"},{"key":"20_CR25","unstructured":"Leonardi, S.: Private communication (2008)"},{"key":"20_CR26","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":"20_CR27","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.) APPROX 2009. LNCS, vol.\u00a05687, pp. 326\u2013338. Springer, Heidelberg (2009)"},{"issue":"4","key":"20_CR28","doi-asserted-by":"publisher","first-page":"245","DOI":"10.1007\/s00453-004-1112-3","volume":"40","author":"C. Swamy","year":"2004","unstructured":"Swamy, C., Kumar, A.: Primal\u2013dual algorithms for connected facility location problems. Algorithmica\u00a040(4), 245\u2013269 (2004)","journal-title":"Algorithmica"},{"key":"20_CR29","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\u2013480. Springer, Heidelberg (2002)"},{"issue":"4","key":"20_CR30","doi-asserted-by":"publisher","first-page":"424","DOI":"10.1007\/s10878-007-9127-8","volume":"17","author":"G. Xu","year":"2009","unstructured":"Xu, G., Xu, J.: An improved approximation algorithm for uncapacitated facility location problem with penalties. Journal of Combinatorial Optimization\u00a017(4), 424\u2013436 (2009)","journal-title":"Journal of Combinatorial Optimization"}],"container-title":["Lecture Notes in Computer Science","Integer Programming and Combinatoral Optimization"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-20807-2_20","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,6]],"date-time":"2025-03-06T10:03:34Z","timestamp":1741255414000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-20807-2_20"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011]]},"ISBN":["9783642208065","9783642208072"],"references-count":30,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-20807-2_20","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2011]]}}}