{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,25]],"date-time":"2026-03-25T16:18:26Z","timestamp":1774455506819,"version":"3.50.1"},"reference-count":44,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2005,10,1]],"date-time":"2005-10-01T00:00:00Z","timestamp":1128124800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2005,10]]},"abstract":"\n Given an undirected graph\n G<\/jats:italic>\n = (\n V,E<\/jats:italic>\n ) with\nnonnegative costs on its edges, a root node\n r<\/jats:italic>\n V<\/jats:italic>\n , a\nset of demands\n D<\/jats:italic>\n V<\/jats:italic>\n with demand\n v<\/jats:italic>\n D<\/jats:italic>\n wishing to route\n w(v)<\/jats:italic>\n units of flow (weight) to\n r<\/jats:italic>\n ,\nand a positive number\n k<\/jats:italic>\n , the\n Capacitated Minimum Steiner\nTree<\/jats:italic>\n (CMStT) problem asks for a minimum Steiner tree, rooted at\n r<\/jats:italic>\n , spanning the vertices in\n D<\/jats:italic>\n *\n&lcub;\n r<\/jats:italic>\n &rcub;, in which the sum of the vertex\nweights in every subtree connected to\n r<\/jats:italic>\n is at most\n k<\/jats:italic>\n .\nWhen\n D<\/jats:italic>\n &equals;\n V<\/jats:italic>\n , this problem is known as the\n Capacitated Minimum Spanning Tree<\/jats:italic>\n (CMST) problem. Both CMsT\nand CMST problems are NP-hard. In this article, we present\napproximation algorithms for these problems and several of their\nvariants in network design. Our main results are the following:\n <\/jats:p>\n \n ---We present a (\u00b3 \u00c1\n \n ST<\/jats:italic>\n <\/jats:sub>\n +\n2)-approximation algorithm for the CMStT problem, where \u00b3 is\nthe\n inverse Steiner ratio<\/jats:italic>\n , and \u00c1\n \n ST<\/jats:italic>\n <\/jats:sub>\n is the best achievable approximation ratio for the Steiner tree\nproblem. Our ratio improves the current best ratio of\n2\u00c1\n \n ST<\/jats:italic>\n <\/jats:sub>\n + 2 for this problem.\n <\/jats:p>\n ---In particular, we obtain (\u00b3 + 2)-approximation ratio for\nthe CMST problem, which is an improvement over the current best\nratio of 4 for this problem. For points in Euclidean and\nrectilinear planes, our result translates into ratios of 3.1548 and\n3.5, respectively.<\/jats:p>\n \n ---For instances in the plane, under the\n L<\/jats:italic>\n \n p<\/jats:italic>\n <\/jats:sub>\n norm, with the vertices in\n D<\/jats:italic>\n having uniform weights, we present a nontrivial\n(7\/5\u00c1\n \n ST<\/jats:italic>\n <\/jats:sub>\n + 3\/2)-approximation algorithm for\nthe CMStT problem. This translates into a ratio of 2.9 for the CMST\nproblem with uniform vertex weights in the\n L<\/jats:italic>\n \n p<\/jats:italic>\n <\/jats:sub>\n metric plane. Our ratio of 2.9 solves\nthe long-standing open problem of obtaining any ratio better than 3\nfor this case.\n <\/jats:p>\n \n ---For the CMST problem, we show how to obtain a 2-approximation\nfor graphs in metric spaces with unit vertex weights and\n k<\/jats:italic>\n =\n3,4.\n <\/jats:p>\n \n ---For the\n budgeted<\/jats:italic>\n CMST problem, in which the weights of\nthe subtrees connected to\n r<\/jats:italic>\n could be up to \u00b1\n k<\/jats:italic>\n instead of\n k<\/jats:italic>\n (\u00b1 e 1), we obtain a ratio of \u00b3\n&plus; 2\/\u00b1.\n <\/jats:p>","DOI":"10.1145\/1103963.1103967","type":"journal-article","created":{"date-parts":[[2006,2,6]],"date-time":"2006-02-06T15:07:09Z","timestamp":1139238429000},"page":"265-282","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":37,"title":["Approximation algorithms for the capacitated minimum spanning tree problem and its variants in network design"],"prefix":"10.1145","volume":"1","author":[{"given":"Raja","family":"Jothi","sequence":"first","affiliation":[{"name":"National Institutes of Health, Bethesda, MD"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Balaji","family":"Raghavachari","sequence":"additional","affiliation":[{"name":"University of Texas at Dallas, Richardson, TX"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2005,10]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"Aarts E. and Korst J. 1989. Simulated Annealing and Boltzman Machines. Wiley Chichester U.K.]] Aarts E. and Korst J. 1989. Simulated Annealing and Boltzman Machines. Wiley Chichester U.K.]]"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-6377(02)00236-5"},{"key":"e_1_2_1_3_1","first-page":"331","article-title":"Heuristics with constant error guarantees for the design of tree networks. Manage","volume":"34","author":"Altinkemer K.","year":"1988","unstructured":"Altinkemer , K. , and Gavish , B. 1988 . Heuristics with constant error guarantees for the design of tree networks. Manage . Sci. 34 , 331 -- 341 .]] Altinkemer, K., and Gavish, B. 1988. Heuristics with constant error guarantees for the design of tree networks. Manage. Sci. 34, 331--341.]]","journal-title":"Sci."},{"key":"e_1_2_1_4_1","first-page":"9","article-title":"Capacitated minimum spanning trees: Algorithms using intelligent search","volume":"1","author":"Amberg A.","year":"1996","unstructured":"Amberg , A. , Domschke , W. , and Vo\u00df , S. 1996 . Capacitated minimum spanning trees: Algorithms using intelligent search . Comb. Opt.: Theor. Pract. 1 , 9 -- 39 .]] Amberg, A., Domschke, W., and Vo\u00df, S. 1996. Capacitated minimum spanning trees: Algorithms using intelligent search. Comb. Opt.: Theor. Pract. 1, 9--39.]]","journal-title":"Comb. Opt.: Theor. Pract."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCOM.1977.1093708"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230030204"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/T-C.1972.223452"},{"key":"e_1_2_1_8_1","doi-asserted-by":"crossref","unstructured":"Domschke W. Forst P. and Vo\u00df S. 1992. Tabu search techniques for the quadratic semi-assignment problem. In New Directions for Operations Research in Manufacturing. Springer Berlin Germany 389--405.]] Domschke W. Forst P. and Vo\u00df S. 1992. Tabu search techniques for the quadratic semi-assignment problem. In New Directions for Operations Research in Manufacturing. Springer Berlin Germany 389--405.]]","DOI":"10.1007\/978-3-642-77537-6_23"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCOM.1974.1092122"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1147\/sj.53.0142"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230010105"},{"key":"e_1_2_1_12_1","unstructured":"Garey M. and Johnson D. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman San Francisco CA.]] Garey M. and Johnson D. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman San Francisco CA.]]"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230120402"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/322358.322367"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCOM.1985.1096250"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02061657"},{"key":"e_1_2_1_17_1","volume-title":"Proceedings of the IEEE INFOCOM. 130--139","author":"Gavish B.","unstructured":"Gavish , B. , and Altinkemer , K . 1986. Parallel savings heuristics for the topological design of local access tree networks . In Proceedings of the IEEE INFOCOM. 130--139 .]] Gavish, B., and Altinkemer, K. 1986. Parallel savings heuristics for the topological design of local access tree networks. In Proceedings of the IEEE INFOCOM. 130--139.]]"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1287\/ijoc.1.3.190"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1287\/ijoc.2.1.4"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793242618"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02136155"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.43.1.130"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02071978"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1287\/ijoc.8.3.219"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.5555\/646688.703097"},{"key":"e_1_2_1_26_1","volume-title":"Proceedings of the 31st International Colloquium on Automata, Languages and Programming (ICALP). 805--818","author":"Jothi R.","unstructured":"Jothi , R. , and Raghavachari , B . 2004a. Approximation algorithms for the capacitated minimum spanning problem and its variants in network design . In Proceedings of the 31st International Colloquium on Automata, Languages and Programming (ICALP). 805--818 .]] Jothi, R., and Raghavachari, B. 2004a. Approximation algorithms for the capacitated minimum spanning problem and its variants in network design. In Proceedings of the 31st International Colloquium on Automata, Languages and Programming (ICALP). 805--818.]]"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2004.04.007"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCOM.1976.1093334"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230040403"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230130211"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCOM.1980.1094601"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCOM.1974.1092123"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230230603"},{"key":"e_1_2_1_34_1","volume-title":"Design of Real-Time Computer Systems","author":"Martin J.","unstructured":"Martin , J. 1967. Design of Real-Time Computer Systems . Prentice Hall , Englewood Cliffs, NJ .]] Martin, J. 1967. Design of Real-Time Computer Systems. Prentice Hall, Englewood Cliffs, NJ.]]"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCOM.1977.1093710"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02293049"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1016\/0969-6016(94)90032-9"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230080306"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02570700"},{"key":"e_1_2_1_40_1","volume-title":"Proceedings of the 8th ACM-SIAM Symposium on Discrete Algorithms (SODA). 619--628","author":"Salman F.","unstructured":"Salman , F. , Cheriyan , J. , Ravi , R. , and Subramanian , S . 1997. Buy-at-bulk network design: Approximating the single-sink edge installation problem . In Proceedings of the 8th ACM-SIAM Symposium on Discrete Algorithms (SODA). 619--628 .]] Salman, F., Cheriyan, J., Ravi, R., and Subramanian, S. 1997. Buy-at-bulk network design: Approximating the single-sink edge installation problem. In Proceedings of the 8th ACM-SIAM Symposium on Discrete Algorithms (SODA). 619--628.]]"},{"key":"e_1_2_1_41_1","first-page":"563","article-title":"An algorithm for the design of multilevel concentrator networks","volume":"6","author":"Schneider G.","year":"1982","unstructured":"Schneider , G. , and Zastrow , M. 1982 . An algorithm for the design of multilevel concentrator networks . Comput. Netw. 6 , 563 -- 581 .]] Schneider, G., and Zastrow, M. 1982. An algorithm for the design of multilevel concentrator networks. Comput. Netw. 6, 563--581.]]","journal-title":"Comput. Netw."},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1097-0037(199705)29:3<161::AID-NET4>3.0.CO;2-F"},{"key":"e_1_2_1_43_1","volume-title":"Proceedings of the IEEE International Conference on Communications. 19","author":"Sharma R.","unstructured":"Sharma , R. , and El-Bardai , M . 1970. Suboptimal communications network synthesis . In Proceedings of the IEEE International Conference on Communications. 19 .11--19.16.]] Sharma, R., and El-Bardai, M. 1970. Suboptimal communications network synthesis. In Proceedings of the IEEE International Conference on Communications. 19.11--19.16.]]"},{"key":"e_1_2_1_44_1","volume-title":"Encyclopedia of Optimization","author":"Vo\u00df S.","unstructured":"Vo\u00df , S. 2001. Capacitated minimum spanning trees . In Encyclopedia of Optimization . Kluwer , Boston, MA , 225--235.]] Vo\u00df, S. 2001. Capacitated minimum spanning trees. In Encyclopedia of Optimization. Kluwer, Boston, MA, 225--235.]]"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1103963.1103967","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1103963.1103967","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T22:48:54Z","timestamp":1750286934000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1103963.1103967"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005,10]]},"references-count":44,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2005,10]]}},"alternative-id":["10.1145\/1103963.1103967"],"URL":"https:\/\/doi.org\/10.1145\/1103963.1103967","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2005,10]]},"assertion":[{"value":"2005-10-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}