{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,1,10]],"date-time":"2025-01-10T16:10:07Z","timestamp":1736525407617,"version":"3.32.0"},"publisher-location":"Berlin, Heidelberg","reference-count":29,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540380443"},{"type":"electronic","value":"9783540380450"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2006]]},"DOI":"10.1007\/11830924_16","type":"book-chapter","created":{"date-parts":[[2006,8,25]],"date-time":"2006-08-25T12:33:54Z","timestamp":1156509234000},"page":"152-163","source":"Crossref","is-referenced-by-count":8,"title":["Approximating Buy-at-Bulk and Shallow-Light k-Steiner Trees"],"prefix":"10.1007","author":[{"given":"M. T.","family":"Hajiaghayi","sequence":"first","affiliation":[]},{"given":"G.","family":"Kortsarz","sequence":"additional","affiliation":[]},{"given":"M. R.","family":"Salavatipour","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"doi-asserted-by":"crossref","unstructured":"Andrews, M.: Hardness of Buy-at-Bulk Network Design. In: Proceedings of FOCS 2004, pp. 115\u2013124 (2004)","key":"16_CR1","DOI":"10.1109\/FOCS.2004.32"},{"issue":"2","key":"16_CR2","doi-asserted-by":"publisher","first-page":"197","DOI":"10.1007\/s00453-002-0968-3","volume":"34","author":"M. Andrews","year":"2002","unstructured":"Andrews, M., Zhang, L.: Approximation algorithms for access network design. Algorithmica\u00a034(2), 197\u2013215 (2002)","journal-title":"Algorithmica"},{"doi-asserted-by":"crossref","unstructured":"Awerbuch, B., Azar, Y.: Buy-at-bulk network design. In: Proceedings of FOCS 1997, pp. 542\u2013547 (1997)","key":"16_CR3","DOI":"10.1109\/SFCS.1997.646143"},{"issue":"1","key":"16_CR4","doi-asserted-by":"publisher","first-page":"254","DOI":"10.1137\/S009753979528826X","volume":"28","author":"B. Awerbuch","year":"1999","unstructured":"Awerbuch, B., Azar, Y., Blum, A., Vempala, S.: New approximation guarantees for minimum-weight k-trees and prize-collecting salesmen. SIAM Journal on Computing\u00a028(1), 254\u2013262 (1999)","journal-title":"SIAM Journal on Computing"},{"key":"16_CR5","doi-asserted-by":"publisher","first-page":"179","DOI":"10.1016\/S0304-3975(99)00130-9","volume":"250","author":"J. Bar-Ilan","year":"2001","unstructured":"Bar-Ilan, J., Kortsarz, G., Peleg, D.: Generalized submodular cover problems and applications. Theoretical Computer Science\u00a0250, 179\u2013200 (2001)","journal-title":"Theoretical Computer Science"},{"doi-asserted-by":"crossref","unstructured":"Bartal, Y.: On approximating arbitrary matrices by tree metrics. In: Proceedings of STOC, pp. 161\u2013168 (1998)","key":"16_CR6","DOI":"10.1145\/276698.276725"},{"doi-asserted-by":"crossref","unstructured":"Blum, A., Ravi, R., Vempala, S.: A constant-factor approximation algorithm for the k MST problem (extended abstract). In: Proceedings of STOC 1996, pp. 442\u2013448 (1996)","key":"16_CR7","DOI":"10.1145\/237814.237992"},{"doi-asserted-by":"crossref","unstructured":"Charikar, M., Karagiozova, A.: On non-uniform multicommodity buy-at-bulk network design. In: Proceedings of STOC 2005, pp. 176\u2013182 (2005)","key":"16_CR8","DOI":"10.1145\/1060590.1060617"},{"unstructured":"Chekuri, C., Khanna, S., Naor, J.: A deterministic algorithm for the cost-distance problem. In: Proceedings of SODA 2001, pp. 232\u2013233 (2001)","key":"16_CR9"},{"unstructured":"Chuzhoy, J., Gupta, A., Naor, J., Sinha, A.: On the approximability of some network design problems. In: Proceedings of SODA 2005, pp. 943\u2013951 (2005)","key":"16_CR10"},{"doi-asserted-by":"crossref","unstructured":"Chekuri, C., Hajiaghayi, M., Kortsarz, G., Salavatipour, M.: Approximation Algorithms for Non-Uniform Buy-at-Bulk Network Design Problems (submitted, 2006)","key":"16_CR11","DOI":"10.1109\/FOCS.2006.15"},{"issue":"3","key":"16_CR12","first-page":"595","volume":"11","author":"J. Cheriyan","year":"2000","unstructured":"Cheriyan, J., Salman, F.S., Ravi, R., Subramanian, S.: Buy-at-bulk network design: Approximating the single-sink edge installation problem. SIAM Journal on Optimization\u00a011(3), 595\u2013610 (2000)","journal-title":"SIAM Journal on Optimization"},{"issue":"3","key":"16_CR13","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"},{"issue":"3","key":"16_CR14","doi-asserted-by":"publisher","first-page":"410","DOI":"10.1007\/s004530010050","volume":"29","author":"U. Feige","year":"2001","unstructured":"Feige, U., Kortsarz, G., Peleg, D.: The dense k-subgraph problem. Algorithmica\u00a029(3), 410\u2013421 (2001)","journal-title":"Algorithmica"},{"doi-asserted-by":"crossref","unstructured":"Garg, N.: A 3-Approximation for the minimum tree spanning k vertices. In: Proceedings FOCS 1996, pp. 302\u2013309 (1996)","key":"16_CR15","DOI":"10.1109\/SFCS.1996.548489"},{"doi-asserted-by":"crossref","unstructured":"Garg, N.: Saving an epsilon: a 2-approximation for the k-MST problem in graphs. In: Proceedings of STOC 2005, pp. 396\u2013402 (2005)","key":"16_CR16","DOI":"10.1145\/1060590.1060650"},{"doi-asserted-by":"crossref","unstructured":"Guha, S., Meyerson, A., Munagala, K.: A constant factor approximation for the single sink edge installation problems. In: Proceedings of STOC 2001, pp. 383\u2013388 (2001)","key":"16_CR17","DOI":"10.1145\/380752.380827"},{"doi-asserted-by":"crossref","unstructured":"Guha, S., Meyerson, A., Munagala, K.: Hierarchical placement and network design problems. In: Proceedings of FOCS 2001, pp. 603\u2013612 (2001)","key":"16_CR18","DOI":"10.1109\/SFCS.2000.892328"},{"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: Proceedings of FOCS 2003, pp. 606\u2013617 (2003)","key":"16_CR19","DOI":"10.1109\/SFCS.2003.1238233"},{"doi-asserted-by":"crossref","unstructured":"Gupta, A., Kumar, A., Roughgarden, T.: Simpler and better approximation algorithms for network design. In: Proceedings STOC 2003, pp. 365\u2013372 (2003)","key":"16_CR20","DOI":"10.1145\/780542.780597"},{"doi-asserted-by":"crossref","unstructured":"Hajiaghayi, M.T., Jain, K.: The Prize-Collecting Generalized Steiner Tree Problem via a new approach of Primal-Dual Schema. In: Proceedings of SODA 2006, pp. 631\u2013640 (2006)","key":"16_CR21","DOI":"10.1145\/1109557.1109626"},{"issue":"1","key":"16_CR22","doi-asserted-by":"publisher","first-page":"36","DOI":"10.1287\/moor.17.1.36","volume":"17","author":"R. Hassin","year":"1992","unstructured":"Hassin, R.: Approximation schemes for the restricted shortest path problem. Mathematics of Operations Research\u00a017(1), 36\u201342 (1992)","journal-title":"Mathematics of Operations Research"},{"key":"16_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"175","DOI":"10.1007\/3-540-45753-4_16","volume-title":"Approximation Algorithms for Combinatorial Optimization","author":"R. Hassin","year":"2002","unstructured":"Hassin, R., Levin, A.: Minimum Restricted Diameter Spanning trees. In: Jansen, K., Leonardi, S., Vazirani, V.V. (eds.) APPROX 2002. LNCS, vol.\u00a02462, pp. 175\u2013184. Springer, Heidelberg (2002)"},{"key":"16_CR24","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. Journal of Computer and System Sciences\u00a09, 256\u2013278 (1974)","journal-title":"Journal of Computer and System Sciences"},{"doi-asserted-by":"crossref","unstructured":"Kumar, A., Gupta, A., Roughgarden, T.: A Constant-Factor Approximation Algorithm for the Multicommodity Rent-or-Buy Problem. In: Proceedings of FOCS 2002, pp. 333\u2013342 (2002)","key":"16_CR25","DOI":"10.1109\/SFCS.2002.1181956"},{"issue":"1","key":"16_CR26","doi-asserted-by":"publisher","first-page":"141","DOI":"10.1006\/jagm.1998.0930","volume":"28","author":"M. Marathe","year":"1998","unstructured":"Marathe, M., Ravi, R., Sundaram, R., Ravi, S.S., Rosenkrantz, D., Hunt, H.: Bicriteria network design problems. J. Algorithms\u00a028(1), 141\u2013171 (1998)","journal-title":"J. Algorithms"},{"doi-asserted-by":"crossref","unstructured":"Meyerson, A., Munagala, K., Plotkin, S.: Cost-Distance: Two Metric Network Design. In: Proceedings of FOCS 2000, pp. 383\u2013388 (2000)","key":"16_CR27","DOI":"10.1109\/SFCS.2000.892330"},{"doi-asserted-by":"crossref","unstructured":"Moss, A., Rabani, Y.: Approximation algorithms for constrained node weighted steiner tree problems. In: Proceedings of STOC 2001, pp. 373\u2013382 (2001)","key":"16_CR28","DOI":"10.1145\/380752.380826"},{"issue":"2","key":"16_CR29","doi-asserted-by":"publisher","first-page":"178","DOI":"10.1137\/S0895480194266331","volume":"9","author":"R. Ravi","year":"1996","unstructured":"Ravi, R., Sundaram, R., Marathe, M.V., Rosenkrantz, D.J., Ravi, S.: Spanning trees short or small. SIAM Journal on Discrete Mathematics\u00a09(2), 178\u2013200 (1996)","journal-title":"SIAM Journal on Discrete Mathematics"}],"container-title":["Lecture Notes in Computer Science","Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11830924_16.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,10]],"date-time":"2025-01-10T15:29:07Z","timestamp":1736522947000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11830924_16"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006]]},"ISBN":["9783540380443","9783540380450"],"references-count":29,"URL":"https:\/\/doi.org\/10.1007\/11830924_16","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2006]]}}}