{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T18:36:17Z","timestamp":1725474977055},"publisher-location":"Berlin, Heidelberg","reference-count":19,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540496946"},{"type":"electronic","value":"9783540496960"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2006]]},"DOI":"10.1007\/11940128_13","type":"book-chapter","created":{"date-parts":[[2006,11,29]],"date-time":"2006-11-29T00:57:35Z","timestamp":1164761855000},"page":"111-120","source":"Crossref","is-referenced-by-count":24,"title":["Improved Approximation for Single-Sink Buy-at-Bulk"],"prefix":"10.1007","author":[{"given":"Fabrizio","family":"Grandoni","sequence":"first","affiliation":[]},{"given":"Giuseppe F.","family":"Italiano","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"13_CR1","doi-asserted-by":"crossref","unstructured":"Awerbuch, B., Azar, Y.: Buy-at-bulk network design. In: IEEE Symposium on Foundations of Computer Science (FOCS), pp. 542\u2013547 (1997)","DOI":"10.1109\/SFCS.1997.646143"},{"key":"13_CR2","doi-asserted-by":"crossref","unstructured":"Bartal, Y.: Probabilistic approximation of metric spaces and its algorithmic applications. In: IEEE Symposium on Foundations of Computer Science (FOCS), pp. 184\u2013193 (1996)","DOI":"10.1109\/SFCS.1996.548477"},{"key":"13_CR3","doi-asserted-by":"crossref","unstructured":"Bartal, Y.: On approximating arbitrary metrics by tree metrics. In: IEEE Symposium on Foundations of Computer Science (FOCS), pp. 161\u2013168 (1998)","DOI":"10.1145\/276698.276725"},{"key":"13_CR4","unstructured":"Becchetti, L., Konemann, J., Leonardi, S., Pal, M.: Sharing the cost more efficiently: improved approximation for multicommodity rent-or-buy. In: ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 375\u2013384 (2005)"},{"key":"13_CR5","doi-asserted-by":"crossref","unstructured":"Charikar, M., Chekuri, A., Goel, A., Guha, S.: Approximating a finite metric by a small number of tree metrics. In: IEEE Symposium on Foundations of Computer Science (FOCS), pp. 379\u2013388 (1998)","DOI":"10.1109\/SFCS.1998.743488"},{"key":"13_CR6","unstructured":"Eisenbrand, F., Grandoni, F.: An improved approximation algorithm for virtual private network design. In: ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 928\u2013932 (2005)"},{"key":"13_CR7","series-title":"Lecture Notes in Computer Science","first-page":"1152","volume-title":"Automata, Languages and Programming","author":"F. Eisenbrand","year":"2005","unstructured":"Eisenbrand, F., Grandoni, F., Oriolo, G., Skutella, M.: New approaches for virtual private network design. In: Caires, L., Italiano, G.F., Monteiro, L., Palamidessi, C., Yung, M. (eds.) ICALP 2005. LNCS, vol.\u00a03580, pp. 1152\u20131162. Springer, Heidelberg (2005)"},{"key":"13_CR8","doi-asserted-by":"crossref","unstructured":"Fakcharoenphol, J., Rao, S., Talwar, K.: A tight bound on approximating arbitrary metrics by tree metrics. In: ACM Symposium on the Theory of Computing (STOC), pp. 448\u2013455 (2003)","DOI":"10.1145\/780542.780608"},{"key":"13_CR9","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":"13_CR10","doi-asserted-by":"crossref","unstructured":"Guha, S., Meyerson, A., Munagala, K.: A constant factor approximation for the single sink edge installation problem. In: ACM Symposium on the Theory of Computing (STOC), pp. 383\u2013388 (2001)","DOI":"10.1145\/380752.380827"},{"key":"13_CR11","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: ACM Symposium on the Theory of Computing (STOC), pp. 389\u2013398 (2001)","DOI":"10.1145\/380752.380830"},{"key":"13_CR12","unstructured":"Gupta, A., Kumar, A., Pal, M., Roughgarden, T.: Approximation via cost-sharing: simpler and better approximation algorithms for network design (manuscript)"},{"key":"13_CR13","doi-asserted-by":"crossref","unstructured":"Gupta, A., Kumar, A., Pal, M., Roughgarden, T.: Approximation via cost-sharing: a simple approximation algorithm for the multicommodity rent-or-buy problem. In: IEEE Symposium on Foundations of Computer Science (FOCS), pp. 606\u2013617 (2003)","DOI":"10.1109\/SFCS.2003.1238233"},{"key":"13_CR14","unstructured":"Gupta, A., Kumar, A., Roughgarden, T.: A constant-factor approximation algorithm for the multicommodity. In: IEEE Symposium on Foundations of Computer Science (FOCS), pp. 333\u2013344 (2002)"},{"key":"13_CR15","doi-asserted-by":"crossref","unstructured":"Gupta, A., Kumar, A., Roughgarden, T.: Simpler and better approximation algorithms for network design. In: ACM Symposium on the Theory of Computing (STOC), pp. 365\u2013372 (2003)","DOI":"10.1145\/780542.780597"},{"key":"13_CR16","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":"13_CR17","doi-asserted-by":"crossref","unstructured":"Kumar, A., Swamy, C.: Primal-dual algorithms for the connected facility location problem. In: International Workshop on Approximation Algorithms for Combinatorial Optimization, pp. 256\u2013269 (2002)","DOI":"10.1007\/3-540-45753-4_22"},{"key":"13_CR18","doi-asserted-by":"crossref","unstructured":"Meyerson, A., Munagala, K., Plotkin, S.: Cost-distance: two metric network design. In: IEEE Symposium on Foundations of Computer Science (FOCS), pp. 624\u2013630 (2000)","DOI":"10.1109\/SFCS.2000.892330"},{"key":"13_CR19","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)"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Computation"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11940128_13.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T03:49:42Z","timestamp":1619495382000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11940128_13"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006]]},"ISBN":["9783540496946","9783540496960"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/11940128_13","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2006]]}}}