{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,12]],"date-time":"2026-05-12T14:20:53Z","timestamp":1778595653003,"version":"3.51.4"},"reference-count":23,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"6","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2009,1]]},"DOI":"10.1137\/050643635","type":"journal-article","created":{"date-parts":[[2009,3,30]],"date-time":"2009-03-30T15:34:08Z","timestamp":1238427248000},"page":"2426-2442","source":"Crossref","is-referenced-by-count":17,"title":["A Constant Factor Approximation for the Single Sink Edge Installation Problem"],"prefix":"10.1137","volume":"38","author":[{"given":"Sudipto","family":"Guha","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Adam","family":"Meyerson","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kamesh","family":"Munagala","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"351","reference":[{"key":"10.1137\/050643635_r1","doi-asserted-by":"crossref","unstructured":"M. Andrews,Hardness of buy-at-bulk network design, in Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science, IEEE Computer Society, Washington, DC, 2004, pp. 115\u2013124.","DOI":"10.1109\/FOCS.2004.32"},{"key":"10.1137\/050643635_r2","doi-asserted-by":"crossref","unstructured":"M. Andrews and L. Zhang,The access network design problem, in Proceedings of the 39th Annual IEEE Symposium on Foundations of Computer Science, IEEE Computer Society, Washington, DC, 1998, pp. 40\u201349.","DOI":"10.1109\/SFCS.1998.743427"},{"key":"10.1137\/050643635_r3","doi-asserted-by":"crossref","unstructured":"B. Awerbuch and Y. Azar,Buy-at-bulk network design, in Proceedings of the 38th Annual IEEE Symposium on Foundations of Computer Science, IEEE Computer Society, Washington, DC, 1997, pp. 542\u201347.","DOI":"10.1109\/SFCS.1997.646143"},{"key":"10.1137\/050643635_r4","doi-asserted-by":"crossref","unstructured":"Y. Bartal,On approximating arbitrary metrics by tree metrics, in Proceedings of the 30th Annual ACM Symposium on Theory of Computing, ACM, New York, 1998, pp. 161\u2013168.","DOI":"10.1145\/276698.276725"},{"key":"10.1137\/050643635_r5","unstructured":"M. Charikar, C. Chekuri, A. Goel, S. Guha, and S. Plotkin,Approximating a finite metric by a small number of tree metrics, in Proceedings of the 39th Annual IEEE Symposium on Foundations of Computer Science, IEEE Computer Society, Washington, DC, 1998."},{"key":"10.1137\/050643635_r6","doi-asserted-by":"crossref","unstructured":"M. Charikar and A. Karagiozova,On non-uniform multicommodity buy-at-bulk network design, in Proceedings of the ACM Symposium on Theory of Computing, ACM, New York, 2005, pp. 176\u2013182.","DOI":"10.1145\/1060590.1060617"},{"key":"10.1137\/050643635_r7","doi-asserted-by":"crossref","unstructured":"C. Chekuri, M. T. Hajiaghayi, G. Kortsarz, and M. R. Salavatipour,Approximation algorithms for non-uniform buy-at-bulk network design, in Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science, IEEE Computer Society, Washington, DC, 2006, pp. 677\u2013686.","DOI":"10.1109\/FOCS.2006.15"},{"key":"10.1137\/050643635_r8","unstructured":"J. Chuzhoy, A. Gupta, J. Naor, and A. Sinha,On the approximability of network design problems, in Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms, ACM, New York, SIAM, Philadelphia, 2005, pp. 943\u2013951."},{"key":"10.1137\/050643635_r9","doi-asserted-by":"crossref","unstructured":"J. Fakcharoenphol, S. Rao, and K. Talwar,A tight bound on approximating arbitrary metrics by tree metrics, in Proceedings of the 35th Annual ACM Symposium on Theory of Computing, ACM, New York, 2003, pp. 448\u2013455.","DOI":"10.1145\/780542.780608"},{"key":"10.1137\/050643635_r10","doi-asserted-by":"crossref","unstructured":"N. Garg, R. Khandekar, G. Konjevod, R. Ravi, F. S. Salman, and A. Sinha,On the integrality gap of a natural formulation of the single-sink buy-at-bulk network design problem, in Proceedings of the 8th International IPCO Conference on Integer Programming and Combinatorial Optimization, Springer-Verlag, London, 2001, pp. 170\u2013184.","DOI":"10.1007\/3-540-45535-3_14"},{"key":"10.1137\/050643635_r11","unstructured":"A. Goel and D. Estrin,Simultaneous optimization for concave costs: Single sink aggregation or single source buy-at-bulk, in Proceedings of the ACM-SIAM Symposium on Discrete Algorithms, ACM, New York, SIAM, Philadelphia, 2003, pp. 499\u2013505."},{"key":"10.1137\/050643635_r12","doi-asserted-by":"crossref","unstructured":"S. Guha, A. Meyerson, and K. Munagala,Hierarchical placement and network design problems, in Proceedings of the 41st Annual IEEE Symposium on Foundation of Computer Science, IEEE Computer Society, Washington, DC, 2000, pp. 603\u2013612.","DOI":"10.1109\/SFCS.2000.892328"},{"key":"10.1137\/050643635_r13","doi-asserted-by":"crossref","unstructured":"S. Guha, A. Meyerson, and K. Munagala,A constant factor approximation for the single sink edge installation problems, in Proceedings of the 33rd Annual ACM Symposium on Theory of Computing, ACM, New York, 2001, pp. 383\u2013388.","DOI":"10.1145\/380752.380827"},{"key":"10.1137\/050643635_r14","unstructured":"S. Guha and K. Munagala,Generalized clustering, in Proceedings of the ACM-SIAM Symposium on Discrete Algorithms, ACM, New York, SIAM, Philadelphia, 2002, pp. 484\u2013485."},{"key":"10.1137\/050643635_r15","doi-asserted-by":"crossref","unstructured":"A. Gupta, A. Kumar, and T. Roughgarden,Simpler and better approximation algorithms for network design, in Proceedings of the 35th Annual ACM Symposium on Theory of Computing, ACM, New York, 2003, pp. 365\u2013372.","DOI":"10.1145\/780596.780597"},{"key":"10.1137\/050643635_r16","doi-asserted-by":"crossref","unstructured":"D. Karger and M. Minkoff,Building Steiner trees with incomplete global knowledge, in Proceedings of the 41st Annual IEEE Syposium of Foundations of Computer Science, IEEE Computer Society, Washington, DC, 2000, pp. 613\u2013623.","DOI":"10.1109\/SFCS.2000.892329"},{"key":"10.1137\/050643635_r17","doi-asserted-by":"crossref","unstructured":"J.-H. Lin and J. S. Vitter,$\\epsilon$-approximations with minimum packing constraint violations, in Proceedings of the 24th Annual ACM Symposium on Theory of Computing, ACM, New York, 1992, pp. 771\u2013782.","DOI":"10.1145\/129712.129787"},{"key":"10.1137\/050643635_r18","doi-asserted-by":"crossref","unstructured":"M. Mahdian, Y. Ye, and J. Zhang,Improved approximation algorithms for metric facility location problems, in Proceedings of the 5th International Workshop on Approximation Algorithms for Combinatorial Optimization, Spinger-Verlag, London, 2002, pp. 229\u2013242.","DOI":"10.1007\/3-540-45753-4_20"},{"key":"10.1137\/050643635_r19","doi-asserted-by":"crossref","unstructured":"A. Meyerson, K. Munagala, and S. Plotkin,Cost-distance: Two metric network design, in Proceedings of the 41st Annual IEEE Symposium on Foundations of Computer Science, IEEE Computer Society, Washington, DC, 2000, pp. 624\u2013630.","DOI":"10.1109\/SFCS.2000.892330"},{"key":"10.1137\/050643635_r20","unstructured":"G. Robins and A. Zelikovsky,Improved Steiner tree approximation in graphs, in Proceedings of the 11th Annual ACM-SIAM Symposium on Discrete Algorithms, ACM, New York, SIAM, Philadelphia, 2000, pp. 770\u2013779."},{"key":"10.1137\/050643635_r21","unstructured":"F. S. Salman, J. Cheriyan, R. Ravi, and S. Subramanian,Buy-at-bulk network design: Approximating the single-sink edge installation problem, in Proceedings of the 8th Annual ACM-SIAM Symposium on Discrete Algorithms, ACM, New York, SIAM, Philadelphia, 1997, pp. 619\u2013628."},{"key":"10.1137\/050643635_r22","doi-asserted-by":"crossref","unstructured":"D. B. Shmoys, E. Tardos, and K. Aardal,Approximation algorithms for facility location problems, in Proceedings of the 29th Annual ACM Symposium on Theory of Computing, ACM, New York, 1997, pp. 265\u2013274.","DOI":"10.1145\/258533.258600"},{"key":"10.1137\/050643635_r23","doi-asserted-by":"crossref","unstructured":"K. Talwar,The single-sink buy-at-bulk LP has constant integrality gap, in Proceedings of IPCO, Spinger-Verlag, London, 2002, pp. 475\u2013486.","DOI":"10.1007\/3-540-47867-1_33"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/050643635","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,8]],"date-time":"2025-02-08T18:58:01Z","timestamp":1739041081000},"score":1,"resource":{"primary":{"URL":"http:\/\/epubs.siam.org\/doi\/10.1137\/050643635"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,1]]},"references-count":23,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2009,1]]}},"alternative-id":["10.1137\/050643635"],"URL":"https:\/\/doi.org\/10.1137\/050643635","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,1]]}}}