{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,1]],"date-time":"2025-10-01T16:13:17Z","timestamp":1759335197323},"publisher-location":"Berlin, Heidelberg","reference-count":17,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540436768"},{"type":"electronic","value":"9783540478676"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2002]]},"DOI":"10.1007\/3-540-47867-1_33","type":"book-chapter","created":{"date-parts":[[2007,5,23]],"date-time":"2007-05-23T14:47:17Z","timestamp":1179931637000},"page":"475-486","source":"Crossref","is-referenced-by-count":34,"title":["The Single-Sink Buy-at-Bulk LP Has Constant Integrality Gap"],"prefix":"10.1007","author":[{"given":"Kunal","family":"Talwar","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2002,5,21]]},"reference":[{"key":"33_CR1","doi-asserted-by":"crossref","unstructured":"M. Andrews, L. Zhang. \u201cThe access network design problem\u201d, Proceedings of the 39th Annual IEEE Symposium on Foundations of Computer Science, 42\u201349, 1998.","DOI":"10.1109\/SFCS.1998.743427"},{"key":"33_CR2","doi-asserted-by":"crossref","unstructured":"B. Awerbuch, Y. Azar. \u201cBuy-at-bulk network design\u201d, Proceedings of the 38th Annual IEEE Symposium on Foundations of Computer Science, 542\u2013547, 1997.","DOI":"10.1109\/SFCS.1997.646143"},{"key":"33_CR3","doi-asserted-by":"crossref","unstructured":"Y. Bartal. \u201cProbabilistic approximation of metric spaces and its algorithmic applications\u201d, Proceedings of the 37th Annual IEEE Symposium on Foundations of Computer Science, 184\u2013193, 1996.","DOI":"10.1109\/SFCS.1996.548477"},{"key":"33_CR4","doi-asserted-by":"crossref","unstructured":"Y. Bartal. \u201cOn approximating arbitrary metrics by tree metrics\u201d, Proceedings of the 30th Annual ACM Symposium on Theory of Computing, 161\u2013168, 1998.","DOI":"10.1145\/276698.276725"},{"key":"33_CR5","first-page":"311","volume-title":"Anottated bibliographies in combinatorial optimization","author":"A. Balakrishnan","year":"1997","unstructured":"A. Balakrishnan, T. Magnanti, P. Mirchandani. \u201cNetwork Design\u201d, in Anottated bibliographies in combinatorial optimization, M. Dell\u2019Amico, F. Maffioli and S. Martello(eds.), John Wiley and Sons, New York, 311\u2013334, 1997."},{"key":"33_CR6","doi-asserted-by":"crossref","unstructured":"M. Charikar, C. Chekuri, A. Goel, S. Guha. \u201cApproximating a finite metric by a small number of tree metrics, Proceedings of the 39th Symposium on Foundations of Computer Science, 379\u2013388, 1998.","DOI":"10.1109\/SFCS.1998.743488"},{"key":"33_CR7","doi-asserted-by":"crossref","unstructured":"B. Chandra, G. Das, G. Narasimhan, J. Soares. \u201cNew sparseness results for graph spanners\u201d, Proc. of 8th Symposium on Computational Geometry, 192\u2013201, 1992.","DOI":"10.1145\/142675.142717"},{"key":"33_CR8","unstructured":"R. Epstein. \u201cLinear programming and capacitated network loading\u201d, Ph.D. Thesis, MIT, 1998."},{"key":"33_CR9","series-title":"Lect Notes Comput Sci","doi-asserted-by":"publisher","first-page":"170","DOI":"10.1007\/3-540-45535-3_14","volume-title":"Proceedings of the Eighth International Conference on Integer Programming and Combinatorial Optimization","author":"N. Garg","year":"2001","unstructured":"N. Garg, R. Khandekar, G. Konjevod, R. Ravi, F.S. Salman, A. Sinha. \u201cOn the integrality gap of a natural formulation of the single-sink buy-at-bulk network design problem\u201d, Proceedings of the Eighth International Conference on Integer Programming and Combinatorial Optimization, Lecture Notes in Computer Science 2081, Springer, 170\u2013184, 2001."},{"key":"33_CR10","doi-asserted-by":"crossref","unstructured":"S. Guha, A. Meyerson, K. Munagala. \u201cA constant factor approximation for the single sink edge installation problem\u201d, Proceedings of the 33rd Annual ACM Symposium on Theory of Computing, 383\u2013388, 2001.","DOI":"10.1145\/380752.380827"},{"key":"33_CR11","series-title":"Lect Notes Comput Sci","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1007\/3-540-44436-X_17","volume-title":"Approximation algorithms for combinatorial optimization, Third International workshop, APPROX 2000, Proceedings","author":"R. Hassin","year":"2000","unstructured":"R. Hassin, R. Ravi, F.S. Salman. \u201cApproximation algorithms for a capacitated network design problem\u201d, Approximation algorithms for combinatorial optimization, Third International workshop, APPROX 2000, Proceedings, Lecture Notes in Computer Science 1913, Springer, 167\u2013176, 2000."},{"issue":"4","key":"33_CR12","doi-asserted-by":"publisher","first-page":"305","DOI":"10.1007\/BF01294129","volume":"14","author":"S. Khuller","year":"1994","unstructured":"S. Khuller, B. Raghavachari, N. Young. \u201cBalancing minimum spanning and shortest path trees\u201d, Algorithmica, 14(4):305\u2013321, 1994.","journal-title":"Algorithmica"},{"key":"33_CR13","unstructured":"P. Mirchandani. Ph.D. thesis, MIT, 1989."},{"key":"33_CR14","unstructured":"Y. Mansour, D. Peleg. \u201cAn approximation algorithm for minimum-cost network design\u201d, The Weizman Institute of Science Tech. Report CS94-22."},{"key":"33_CR15","doi-asserted-by":"crossref","unstructured":"A. Meyerson, K. Munagala, S. Plotkin. \u201cCost-distance: Two metric network design\u201d, Proceedings of the 41st Annual IEEE Symposium on Foundations of Computer Science, 624\u2013630, 2000.","DOI":"10.1109\/SFCS.2000.892330"},{"key":"33_CR16","doi-asserted-by":"publisher","first-page":"142","DOI":"10.1287\/opre.43.1.142","volume":"43","author":"T. Magnanti","year":"1995","unstructured":"T. Magnanti, P. Mirchandani, R. Vachani, \u201cModeling and solving the two-facility capacitated network loading problem\u201d, Operations Research 43, 142\u2013157, 1995.","journal-title":"Operations Research"},{"key":"33_CR17","unstructured":"F.S. Salman, J. Cheriyan, R. Ravi, S. Subramanian.\u201d Buy-at-bulk network design: Approximating the single sink edge installation problem\u201d, Proceedings of the 8th Annual ACM-SIAM Symposium on Discrete Algorithms, 619\u2013628, 1997."}],"container-title":["Lecture Notes in Computer Science","Integer Programming and Combinatorial Optimization"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-47867-1_33","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,2,16]],"date-time":"2019-02-16T17:18:40Z","timestamp":1550337520000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-47867-1_33"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2002]]},"ISBN":["9783540436768","9783540478676"],"references-count":17,"URL":"https:\/\/doi.org\/10.1007\/3-540-47867-1_33","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2002]]}}}