article

Approximation algorithms for the capacitated minimum spanning tree problem and its variants in network design

Authors:

Balaji RaghavachariAuthors Info & Claims

ACM Transactions on Algorithms (TALG), Volume 1, Issue 2

Pages 265 - 282

https://doi.org/10.1145/1103963.1103967

Published: 01 October 2005 Publication History

Abstract

Given an undirected graph G = (V,E) with nonnegative costs on its edges, a root node r V, a set of demands D V with demand v D wishing to route w(v) units of flow (weight) to r, and a positive number k, the Capacitated Minimum Steiner Tree (CMStT) problem asks for a minimum Steiner tree, rooted at r, spanning the vertices in D * {r}, in which the sum of the vertex weights in every subtree connected to r is at most k. When D = V, this problem is known as the Capacitated Minimum Spanning Tree (CMST) problem. Both CMsT and CMST problems are NP-hard. In this article, we present approximation algorithms for these problems and several of their variants in network design. Our main results are the following:

---We present a (³ Á_ST + 2)-approximation algorithm for the CMStT problem, where ³ is the inverse Steiner ratio, and Á_ST is the best achievable approximation ratio for the Steiner tree problem. Our ratio improves the current best ratio of 2Á_ST + 2 for this problem.

---In particular, we obtain (³ + 2)-approximation ratio for the CMST problem, which is an improvement over the current best ratio of 4 for this problem. For points in Euclidean and rectilinear planes, our result translates into ratios of 3.1548 and 3.5, respectively.

---For instances in the plane, under the L_p norm, with the vertices in D having uniform weights, we present a nontrivial (7/5Á_ST + 3/2)-approximation algorithm for the CMStT problem. This translates into a ratio of 2.9 for the CMST problem with uniform vertex weights in the L_pmetric plane. Our ratio of 2.9 solves the long-standing open problem of obtaining any ratio better than 3 for this case.

---For the CMST problem, we show how to obtain a 2-approximation for graphs in metric spaces with unit vertex weights and k = 3,4.

---For the budgeted CMST problem, in which the weights of the subtrees connected to r could be up to ± k instead of k (± e 1), we obtain a ratio of ³ + 2/±.

References

[1]

Aarts, E., and Korst, J. 1989. Simulated Annealing and Boltzman Machines. Wiley, Chichester, U.K.]]

Digital Library

[2]

Ahuja, R., Orlin, J., and Sharma, D. 2001. A composite neighborhood search algorithm for the capacitated minimum spanning tree problem. Oper. Res. Letters 31, 185--194.]]

Digital Library

[3]

Altinkemer, K., and Gavish, B. 1988. Heuristics with constant error guarantees for the design of tree networks. Manage. Sci. 34, 331--341.]]

Digital Library

[4]

Amberg, A., Domschke, W., and Voß, S. 1996. Capacitated minimum spanning trees: Algorithms using intelligent search. Comb. Opt.: Theor. Pract. 1, 9--39.]]

[5]

Boorstyn, R., and Frank, H. 1977. Large-scale network topological optimization. IEEE Trans. Comm. 25, 29--47.]]

[6]

Chandy, K., and Lo, T. 1973. The capacitated minimum spanning tree. Networks 3, 173--181.]]

[7]

Chandy, K., and Russell, R. 1972. The design of multipoint linkages in a teleprocessing tree network. IEEE Trans. Comp. 21, 1062--1066.]]

Digital Library

[8]

Domschke, W., Forst, P., and Voß, S. 1992. Tabu search techniques for the quadratic semi-assignment problem. In New Directions for Operations Research in Manufacturing. Springer, Berlin, Germany, 389--405.]]

[9]

Elias, D., and Ferguson, M. 1974. Topological design of multipoint teleprocessing networks. IEEE Trans. Comm. 22, 1753--1762.]]

[10]

Esau, L., and Williams, K. 1966. On teleprocessing system design. IBM Sys. J. 5, 142--147.]]

Digital Library

[11]

Frank, H., Frisch, I., Slyke, R. V., and Chou, W. 1971. Optimal design of centralized computer design network. Networks 1, 43--57.]]

[12]

Garey, M., and Johnson, D. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman, San Francisco, CA.]]

Digital Library

[13]

Gavish, B. 1982. Topological design of centralized computer networks---formulations and algorithms. Networks 12, 355--377.]]

[14]

Gavish, B. 1983. Formulations and algorithms for the capacitated minimal directed tree problem. J. Assoc. Comput. Mach. 30, 118--132.]]

Digital Library

[15]

Gavish, B. 1985. Augmented lagrangean based algorithms for centralized network design. IEEE Trans. Comm. 33, 1247--1257.]]

[16]

Gavish, B. 1991. Topological design of telecommunication networks---local access design methods. Ann. Oper. Res. 33, 1, 17--71.]]

[17]

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.]]

[18]

Glover, F. 1989. Tabu search---part i. ORSA J. Comput. 1, 190--206.]]

[19]

Glover, F. 1990. Tabu search---part ii. ORSA J. Comput. 2, 4--32.]]

[20]

Goemans, M., and Williamson, D. 1995. A general approximation technique for constrained forest problems. SIAM J. Comput. 24, 296--317.]]

Digital Library

[21]

Gouveia, L. 1993. A comparison of directed formulations for the capacitated minimal spanning tree problem. Telecomm. Syst. 1, 51--76.]]

Digital Library

[22]

Gouveia, L. 1995. A 2n constraint formulation for the capacitated minimal spanning tree problem. Oper. Res. 43, 130--141.]]

Digital Library

[23]

Gouveia, L., and Ao, J. P. 1991. Dynamic programming based heuristics for the topological design of local access networks. Ann. Oper. Res. 33, 305--327.]]

[24]

Hall, L. 1996. Experience with a cutting plane approach for the capacitated spanning tree problem. INFORMS J. Comput. 8, 219--234.]]

Digital Library

[25]

Hassin, R., Ravi, R., and Salman, F. 2000. Approximation algorithms for capacitated network design problems. In Proceedings of the Workshop on Approximation Algorithms for Combinatorial Optimization (APPROX). 167--176.]]

Digital Library

[26]

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.]]

[27]

Jothi, R., and Raghavachari, B. 2004b. Survivable network design: The capacitated minimum spanning network problem. Inform Process. Lett. 91, 4, 183--190.]]

Digital Library

[28]

Karnaugh, M. 1976. A new class of algorithms for multipoint network optimization. IEEE Trans. Comm. 24, 500--505.]]

[29]

Kershenbaum, A. 1974. Computing capacitated minimal spanning trees efficiently. Networks 4, 299--310.]]

[30]

Kershenbaum, A., and Boorstyn, R. 1983. Centralized teleprocessing network design. Networks 13, 279--293.]]

[31]

Kershenbaum, A., Boorstyn, R., and Oppenheim, R. 1980. Second-order greedy algorithms for centralized teleprocessing network design. IEEE Trans. Comm. 28, 1835--1838.]]

[32]

Kershenbaum, A., and Chou, W. 1974. A unified algorithm for designing multidrop teleprocessing networks. IEEE Trans. Comm. 22, 1762--1772.]]

[33]

Malik, K., and Yu, G. 1993. A branch and bound algorithm for the capacitated minimum spanning tree problem. Networks 23, 525--532.]]

[34]

Martin, J. 1967. Design of Real-Time Computer Systems. Prentice Hall, Englewood Cliffs, NJ.]]

Digital Library

[35]

McGregor, P., and Shen, D. 1977. Network design: An algorithm for the access facility location problem. IEEE Trans. Comm. 25, 61--73.]]

[36]

Monma, C., and Suri, S. 1992. Transitions in geometric minimum spanning trees. Disc. Comput. Geom. 8, 265--293.]]

Digital Library

[37]

Osman, I., and Christofides, N. 1994. Capacitated clustering problems by hybrid simulated annealing and tabu search. Intl. Trans. Oper. Res. 1, 317--336.]]

[38]

Papadimitriou, C. 1978. The complexity of the capacitated tree problem. Networks 8, 217--230.]]

[39]

Robins, G., and Salowe, J. 1995. Low-degree minimum spanning trees. Disc. Comput. Geom. 14, 151--166.]]

Digital Library

[40]

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.]]

Digital Library

[41]

Schneider, G., and Zastrow, M. 1982. An algorithm for the design of multilevel concentrator networks. Comput. Netw. 6, 563--581.]]

[42]

Sharaiha, Y., Gendreau, M., Laporte, G., and Osman, I. 1997. A tabu search algorithm for the capacitated shortest spanning tree problem. Networks 29, 161--171.]]

[43]

Sharma, R., and El-Bardai, M. 1970. Suboptimal communications network synthesis. In Proceedings of the IEEE International Conference on Communications. 19.11--19.16.]]

[44]

Voß, S. 2001. Capacitated minimum spanning trees. In Encyclopedia of Optimization. Kluwer, Boston, MA, 225--235.]]

[45]

Whitney, V. 1970. A study of optimal file assignment and communication network configuration in remote access computer message processing and communications systems. Ph.D. Dissertation. University of Michigan, Ann Arbor, MI.]]

Digital Library

Cited By

Jowhari HNematollahi S(2025)Airports and railways with unsplittable demandInformation Processing Letters10.1016/j.ipl.2024.106538188(106538)Online publication date: Feb-2025
https://doi.org/10.1016/j.ipl.2024.106538
Pérez-Rúa JLund RVerelst DAbrahamsen ADykes K(2024)Exact optimization of inter-array dynamic cable networks for Floating Offshore Wind FarmsRenewable Energy10.1016/j.renene.2024.121647237(121647)Online publication date: Dec-2024
https://doi.org/10.1016/j.renene.2024.121647
Salavatipour MTian L(2024)Approximation algorithms for the airport and railway problemJournal of Combinatorial Optimization10.1007/s10878-024-01237-449:1Online publication date: 4-Dec-2024
https://dl.acm.org/doi/10.1007/s10878-024-01237-4
Show More Cited By

Index Terms

Approximation algorithms for the capacitated minimum spanning tree problem and its variants in network design
1. Mathematics of computing
  1. Discrete mathematics
    1. Combinatorics
    2. Graph theory
2. Theory of computation
  1. Design and analysis of algorithms

Recommendations

Degree-bounded minimum spanning trees

Given n points in the Euclidean plane, the degree-@d minimum spanning tree (MST) problem asks for a spanning tree of minimum weight in which the degree of each vertex is at most @d. The problem is NP-hard for 2@__ __@d@__ __3, while the NP-hardness of ...
Low-Degree Spanning Trees of Small Weight

Given $n$ points in the plane, the degree-$K$ spanning-tree problem asks for a spanning tree of minimum weight in which the degree of each vertex is at most $K$. This paper addresses the problem of computing low-weight degree-$K$ spanning trees for $K>2$...
Approximating the Degree-Bounded Minimum Diameter Spanning Tree Problem
Abstract
We consider the problem of finding a minimum diameter spanning tree with maximum node degree $B$ in a complete undirected edge-weighted graph. We provide an $O(\sqrt{\log_Bn})$-approximation algorithm for the problem. Our algorithm is purely ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Algorithms

ACM Transactions on Algorithms Volume 1, Issue 2

October 2005

190 pages

ISSN:1549-6325

EISSN:1549-6333

DOI:10.1145/1103963

Issue’s Table of Contents

Copyright © 2005 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 October 2005

Published in TALG Volume 1, Issue 2

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

36
Total Citations
View Citations
1,809
Total Downloads

Downloads (Last 12 months)31
Downloads (Last 6 weeks)4

Reflects downloads up to 14 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Jowhari HNematollahi S(2025)Airports and railways with unsplittable demandInformation Processing Letters10.1016/j.ipl.2024.106538188(106538)Online publication date: Feb-2025
https://doi.org/10.1016/j.ipl.2024.106538
Pérez-Rúa JLund RVerelst DAbrahamsen ADykes K(2024)Exact optimization of inter-array dynamic cable networks for Floating Offshore Wind FarmsRenewable Energy10.1016/j.renene.2024.121647237(121647)Online publication date: Dec-2024
https://doi.org/10.1016/j.renene.2024.121647
Salavatipour MTian L(2024)Approximation algorithms for the airport and railway problemJournal of Combinatorial Optimization10.1007/s10878-024-01237-449:1Online publication date: 4-Dec-2024
https://dl.acm.org/doi/10.1007/s10878-024-01237-4
Romanuke V(2023)Building Minimum Spanning Trees under Maximum Edge Length ConstraintInformation Technology and Management Science10.7250/itms-2023-000326(17-26)Online publication date: 30-Nov-2023
https://doi.org/10.7250/itms-2023-0003
Zuo TZhang YXie XMeng KTong ZDong ZJia Y(2022)A Review of Optimization Technologies for Large-scale Wind Farm Planning with Practical and Prospective ConcernsIEEE Transactions on Industrial Informatics10.1109/TII.2022.3217282(1-14)Online publication date: 2022
https://doi.org/10.1109/TII.2022.3217282
Chen LTang FKong LLi RHou ZLiu JLi XGuo S(2022)Load-Adaptive and Energy-Efficient Topology Control in LEO Mega-Constellation NetworksGLOBECOM 2022 - 2022 IEEE Global Communications Conference10.1109/GLOBECOM48099.2022.10001189(1552-1557)Online publication date: 4-Dec-2022
https://doi.org/10.1109/GLOBECOM48099.2022.10001189
Pérez-Rúa J(2022)Solver-free heuristics to retrieve feasible points for offshore wind farm collection systemEngineering Optimization10.1080/0305215X.2022.210802755:10(1652-1667)Online publication date: 29-Aug-2022
https://doi.org/10.1080/0305215X.2022.2108027
Li JWang WLichen JLiu SPan P(2022)Approximation algorithms for solving the line-capacitated minimum Steiner tree problemJournal of Global Optimization10.1007/s10898-022-01163-x84:3(687-714)Online publication date: 1-Nov-2022
https://dl.acm.org/doi/10.1007/s10898-022-01163-x
Ganesan G(2021)Minimum spanning trees of random geometric graphs with location dependent weightsBernoulli10.3150/20-BEJ131827:4Online publication date: 1-Nov-2021
https://doi.org/10.3150/20-BEJ1318
Perez-Rua JStolpe MDas KCutululis N(2020)Global Optimization of Offshore Wind Farm Collection SystemsIEEE Transactions on Power Systems10.1109/TPWRS.2019.295731235:3(2256-2267)Online publication date: May-2020
https://doi.org/10.1109/TPWRS.2019.2957312
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Issue’s Table of Contents