{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,13]],"date-time":"2026-02-13T14:48:04Z","timestamp":1770994084450,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":26,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642033667","type":"print"},{"value":"9783642033674","type":"electronic"}],"license":[{"start":{"date-parts":[[2009,1,1]],"date-time":"2009-01-01T00:00:00Z","timestamp":1230768000000},"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":[[2009]]},"DOI":"10.1007\/978-3-642-03367-4_15","type":"book-chapter","created":{"date-parts":[[2009,7,20]],"date-time":"2009-07-20T03:56:42Z","timestamp":1248062202000},"page":"168-180","source":"Crossref","is-referenced-by-count":2,"title":["Approximation Algorithms for Buy-at-Bulk Geometric Network Design"],"prefix":"10.1007","author":[{"given":"Artur","family":"Czumaj","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jurek","family":"Czyzowicz","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Leszek","family":"G\u0105sieniec","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jesper","family":"Jansson","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Andrzej","family":"Lingas","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pawel","family":"Zylinski","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"5","key":"15_CR1","doi-asserted-by":"publisher","first-page":"753","DOI":"10.1145\/290179.290180","volume":"45","author":"S. Arora","year":"1998","unstructured":"Arora, S.: Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems. Journal of the ACM\u00a045(5), 753\u2013782 (1998)","journal-title":"Journal of the ACM"},{"key":"15_CR2","doi-asserted-by":"crossref","unstructured":"Arora, S., Raghavan, P., Rao, S.: Approximation schemes for Euclidean k-medians and related problems. In: Proc. 30th ACM STOC, pp. 106\u2013113 (1998)","DOI":"10.1145\/276698.276718"},{"key":"15_CR3","doi-asserted-by":"crossref","unstructured":"Awerbuch, B., Azar, Y.: Buy-at-bulk network design. In: Proc 38th IEEE FOCS, pp. 542\u2013547 (1997)","DOI":"10.1109\/SFCS.1997.646143"},{"issue":"2","key":"15_CR4","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1007\/BF01581104","volume":"81","author":"D. Bienstock","year":"1998","unstructured":"Bienstock, D., Chopra, S., G\u00fcnl\u00fck, O., Tsai, C.-Y.: Minimum cost capacity installation for multicommodity network flows. Mathematical Programming\u00a081(2), 177\u2013199 (1998)","journal-title":"Mathematical Programming"},{"key":"15_CR5","doi-asserted-by":"crossref","unstructured":"Chekuri, C., Hajiaghayi, M.T., Kortsarz, G., Salavatipour, M.R.: Polylogarithmic approximation algorithms for non-uniform multicommodity buy-at-bulk network design. In: Proc. 47th IEEE FOCS, pp. 677\u2013686 (2006)","DOI":"10.1109\/FOCS.2006.15"},{"key":"15_CR6","unstructured":"Chekuri, C., Hajiaghayi, M.T., Kortsarz, G., Salavatipour, M.R.: Approximation algorithms for node-weighted buy-at-bulk network design. In: SODA, pp. 1265\u20131274 (2007)"},{"issue":"3","key":"15_CR7","doi-asserted-by":"publisher","first-page":"165","DOI":"10.1016\/S0166-218X(98)00024-9","volume":"85","author":"S. Chopra","year":"1998","unstructured":"Chopra, S., Gilboa, I., Sastry, S.T.: Source sink flows with capacity installation in batches. Discrete Applied Mathematics\u00a085(3), 165\u2013192 (1998)","journal-title":"Discrete Applied Mathematics"},{"key":"15_CR8","unstructured":"Czumaj, A., Lingas, A.: On approximability of the minimum-cost k-connected spanning subgraph problem. In: Proc. 10th IEEE-SIAM SODA, pp. 281\u2013290 (1999)"},{"key":"15_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"856","DOI":"10.1007\/3-540-45022-X_72","volume-title":"Automata, Languages and Programming","author":"A. Czumaj","year":"2000","unstructured":"Czumaj, A., Lingas, A.: Fast approximation schemes for euclidean multi-connectivity problems. In: Welzl, E., Montanari, U., Rolim, J.D.P. (eds.) ICALP 2000. LNCS, vol.\u00a01853, pp. 856\u2013868. Springer, Heidelberg (2000)"},{"key":"15_CR10","doi-asserted-by":"crossref","unstructured":"Gupta, A., Kumar, A., Roughgarden, T.: Simpler and better approximation algorithms for network design. In: Proc. 35th ACM STOC, pp. 365\u2013372 (2003)","DOI":"10.1145\/780542.780597"},{"key":"15_CR11","volume-title":"Computers and Intractability. A Guide to the Theory of NP-completeness","author":"M.R. Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability. A Guide to the Theory of NP-completeness. W.H. Freeman and Company, New York (1979)"},{"key":"15_CR12","doi-asserted-by":"crossref","unstructured":"Garg., N., Khandekar, R., Konjevod, G., Ravi, R., Salman, F.S., Sinha, A.: On the integrality gap of a natural formulation of the single-sink buy-at-bulk network design problem. In: Proc. 8th IPCO, pp. 170\u2013184 (2001)","DOI":"10.1007\/3-540-45535-3_14"},{"key":"15_CR13","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":"15_CR14","doi-asserted-by":"crossref","unstructured":"Guha, S., Meyerson, A., Munagala, K.: A constant factor approximation for the single sink edge installation problem. In: Proc. 33rd ACM STOC, pp. 383\u2013399 (2001)","DOI":"10.1145\/380752.380827"},{"key":"15_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1007\/3-540-44436-X_17","volume-title":"Approximation Algorithms for Combinatorial Optimization","author":"R. Hassin","year":"2000","unstructured":"Hassin, R., Ravi, R., Salman, F.S.: Approximation algorithms for a capacitated network design problem. In: Jansen, K., Khuller, S. (eds.) APPROX 2000. LNCS, vol.\u00a01913, pp. 167\u2013176. Springer, Heidelberg (2000)"},{"issue":"2","key":"15_CR16","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1145\/322123.322124","volume":"26","author":"F.K. Hwang","year":"1979","unstructured":"Hwang, F.K.: An O(nlogn) algorithm for rectilinear minimal spanning trees. JACM\u00a026(2), 177\u2013182 (1979)","journal-title":"JACM"},{"key":"15_CR17","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":"15_CR18","unstructured":"Mansour, Y., Peleg, D.: An approximation algorithm for minimum-cost network design. Technical report, The Weizman Institute of Science, Revohot, Israel, CS94-22 (1994)"},{"key":"15_CR19","doi-asserted-by":"crossref","unstructured":"Meyerson, A., Munagala, K., Plotkin, S.: COST-DISTANCE: Two metric network design. In: Proc. 41st IEEE FOCS, pp. 624\u2013630 (2000)","DOI":"10.1109\/SFCS.2000.892330"},{"key":"15_CR20","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1023\/A:1014554606793","volume":"106","author":"M. Minoux","year":"2001","unstructured":"Minoux, M.: Discrete cost multicommodity network optimization problems and exact solution methods. Annals of Operations Research\u00a0106, 19\u201346 (2001)","journal-title":"Annals of Operations Research"},{"key":"15_CR21","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-1098-6","volume-title":"Computational Geometry","author":"F. Preparata","year":"1985","unstructured":"Preparata, F., Shamos, M.: Computational Geometry. Springer, New York (1985)"},{"key":"#cr-split#-15_CR22.1","doi-asserted-by":"crossref","unstructured":"Rao, S.B., Smith, W.D.: Approximating geometrical graphs via ???spanners??? and ???banyans???. In: Proc. ACM STOC, pp. 540???550 (1998);","DOI":"10.1145\/276698.276868"},{"key":"#cr-split#-15_CR22.2","unstructured":"Full version appeared as TR, NEC (1998)"},{"issue":"3","key":"15_CR23","doi-asserted-by":"publisher","first-page":"595","DOI":"10.1137\/S1052623497321432","volume":"11","author":"F.S. Salman","year":"2000","unstructured":"Salman, F.S., Cheriyan, J., Ravi, R., Subramanian, S.: Approximating the single-sink link-installation problem in network design. SIAM J. Optimization\u00a011(3), 595\u2013610 (2000)","journal-title":"SIAM J. Optimization"},{"key":"15_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-47867-1_33","volume-title":"Integer Programming and Combinatorial Optimization","author":"K. Talwar","year":"2002","unstructured":"Talwar, K.: Single-sink buy-at-bulk LP has constant integrality gap. In: Cook, W.J., Schulz, A.S. (eds.) IPCO 2002. LNCS, vol.\u00a02337. Springer, Heidelberg (2002)"},{"issue":"2","key":"15_CR25","doi-asserted-by":"publisher","first-page":"76","DOI":"10.1002\/net.1026","volume":"38","author":"M. Zachariasen","year":"2001","unstructured":"Zachariasen, M.: A catalog of Hanan grid problems. Networks\u00a038(2), 76\u201383 (2001)","journal-title":"Networks"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Data Structures"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-03367-4_15","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,21]],"date-time":"2019-05-21T11:28:46Z","timestamp":1558438126000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-03367-4_15"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009]]},"ISBN":["9783642033667","9783642033674"],"references-count":26,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-03367-4_15","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009]]}}}