An approximation algorithm for the balanced capacitated minimum spanning tree problem

Document Type : Article


Department of Mathematics and Computer Science, Amirkabir University of Technology, Tehran, P.O. Box 15875-4413, Iran



The capacitated minimum spanning tree problem (CMSTP), a well-known combinatorial optimiza-
tion problem, holds a central place in telecommunication network design. This problem is to fi nd a minimum
cost spanning tree with an extra cardinality limitation on the orders of the subtrees incident to a certain root
node. The balanced capacitated minimum spanning tree problem (BCMSTP) is a special case that aims to balance the orders of the subtrees. We show this problem is NP-hard and present two approximation algorithms,
in this paper.
Considering the maximum order of the subtrees Q, we provide a (3 - 1
/Q)-approximation algorithm to find a
balanced solution. We improve this result to a (2:5 + \epsilon)-approximation algorithm (for every given \epsilon > 0), in
the 2d-Euclidean spaces. Also, we present a polynomial time approximation scheme (PTAS) for CMSTP.


References   1. Oncan, T. and Altinel, I.K. Parametric enhancements   of the Esau-Williams heuristic for the capacitated   minimum spanning tree problem", Journal of the   Operational Research Society, 60, pp. 259{267 (2009).   2. Ali, A.I. and Huang, C.H. Balanced spanning forests   and trees", Networks, 21(6), pp. 667{687 (1991).   3. Arkin, E.M., Guttmann-Beck, N., and Hassin, R.   The (K,k)-capacitated spanning tree problem", International   Conference on Algorithmic Applications in   Management, Algorithmic Aspects in Information and   Management, pp. 25{34 (2010).   4. Gavish, B. Topological design of centralized computer   networks-formulations and algorithms", Networks, 12,   pp. 355{377 (1982).   5. Hassin, R., Ravi, R., and Salman, F.S. Approximation   algorithms for capacitated network design   problems", APPROX, pp. 167{176 (2000).   6. Kritikos, M. and Ioannou, G. A greedy heuristic   for the capacitated minimum spanning tree problem",   Journal of the Operational Research Society, 68, pp.   1223{1235 (2017).   7. Ruiza, E., Albareda-Sambola, M., Fernndez, E., et   al. A biased random-key genetic algorithm for the   capacitated minimum spanning tree problem", Journal   Computers and Operations Research, 57, pp. 95{108   (2015).   8. Sharma, R.L. Design of an economical multidrop   network topology with capacity constraints", IEEE   Transactions on Communications, 31, pp. 590{591   (1983).   9. Incel, O.D., Ghosh, A., Krishnamachari, B., et al.   Fast data collection in tree-based wireless sensor   networks", IEEE Transactions on Mobile Computing,   11(1), pp. 86{99 (2012).   10. Vazirani, V.V., Approximation Algorithms, Springer   (2001).   11. Bowerman, R., Hall, B., and Calamai, P. A multi   objective optimization approach to urban school bus   routing: formulation and solution method", Transportation   Research Part A: Policy and Practice, 29,   pp. 107{123 (1995).   12. Ate_, R., Salari, M., Coelho, L.C., et al. The open   vehicle routing problem with decoupling points", European   Journal of Operational Research, 265(1), pp.   316{327 (2018).   13. Jothi, R. and Raghavachari, B. Approximation algorithms   for the capacitated minimum spanning tree   problem and its variants in network design", ACM   Transactions on Algorithms, 1, pp. 265{282 (2005).   14. Martello, S., Pulleyblank, W.R., Toth, P., et al. Balanced   optimization problems", Operations Research   Letters, 3, pp. 275{278 (1984).   15. Bassetto, T. and Mason, F. The 2-period balanced   traveling salesman problem", Working Papers, 154,   Department of applied mathematics, Universit_a C_a   Foscari Venezia (2007).   16. Cappanera, P. and Scutella, M.G. Balanced paths   in a cyclic networks: tractable cases and related   approaches", Networks, 45, pp. 104{111 (2005).   H. Fallah et al./Scientia Iranica, Transactions D: Computer Science & ... 28 (2021) 1479{1492 1491   17. da Cunha, A.S. Formulation and branch-and-cut   algorithm for the minimum cardinality balanced and   connected clustering problem", In Proceedings of   the International Network Optimization Conference   (INOC), Avignon, France, June 12{14 (2019).   18. Feldmann, A.E. and Foschini, L. Balanced partitions   of trees and applications", Algorithmica, 71, pp. 354{   376 (2015).   19. Ficker, A., Spieksma, F.C., and Woeginger, G.J. Balanced   vector optimization", KUL, Research Report   (2016).   20. Kinable, J., Smeulders, B., Delcour, E., et al. Exact   algorithms for the equitable traveling salesman problem",   European Journal of Operational Research, 261,   pp. 475{485 (2017).   21. Youse_khoshbakht, M., Didehvar, F., and Rahmati,   F. An e_ective rank based ant system algorithm   for solving the balanced vehicle routing problem",   International Journal of Industrial Engineering, 23(1),   pp. 13{25 (2016).   22. Zhang, H. Balanced graph partitioning: optimizing   graph cut based on label swapping", International   Conference on Behavioral, Economic and Sociocultural   Computing (BESC), Nanjing, China, 30 Oct.   { 1 Nov. (2015).   23. Gavish, B. and Altinkemer, K. A parallel savings   heuristic for the topological design of local access tree   networks", Proceedings IEEE-INFOCOM'86, pp. 130{   139 (1986).   24. Altinkemer, K. and Gavish, B. Heuristics with constant   error guarantees for the design of tree networks",   Management Science, 34, pp. 331{341 (1988).   25. Gavish, B. Augmented lagrangean based algorithms   for centralized network design", IEEE Transactions on   Communications, 33, pp. 1247{1257 (1985).   26. Kershenbaum, A. and Boorstyn, R. Centralized   teleprocessing network design", Networks, 13, pp. 279{   293 (1983).   27. Ahuja, R., Orlin, J., and Sharma, D. A composite   neighborhood search algorithm for the capacitated   minimum spanning tree problem", Operations Research   Letters, 31, pp. 185{194 (2003).   28. Chandy, K.M. and Lo, T. The capacitated minimum   tree", Networks, 3, pp. 173{182 (1973).   29. Gavish, B. Topological design of telecommunication   networks local access design methods", Annals of   Operations Research, 33, pp. 17{71 (1991).   30. Gouveia, L. A comparison of directed formulations   for the capacitated minimal spanning tree problem",   Telecommunication Systems, 1, pp. 51{76 (1993).   31. Gamvros, I., Golden, B., and Raghavan, S. The multilevel   capacitated minimum spanning tree problem",   INFORMS Journal on Computing, 18, pp. 348{365   (2006).   32. Berger, D., Gendron, B., Potvin, J.Y., et al. Tabu   search for a network loading problem with multiple facilities",   Journal of Heuristics, 6, pp. 253{267 (2000).   33. Salman, F.S., Ravi, R., and Hooker, J. Solving the   local access network design problem", Working paper,   Krannert Graduate School of Management, Purdue   University, West Lafayette (2001).   34. Rothfarb, B. and Goldstein, M.C. The one-terminal   Telpak problem", Operations Research, 19, pp. 156{   169 (1971).   35. Salman, F.S., Cheriyan, J., Ravi, R., et al. Buyat-   bulk network design: Approximating the singlesink   edge installation problem", Proceedings 8th ACMSIAM   Symposium on Discrete Algorithms (SODA),   pp. 619{628 (1997).   36. Jothi, R. and Raghavachari, B. Survivable network   design: The capacitated minimum spanning network   problem", Information Processing Letters, 91, pp.   183{190 (2004).   37. Goemans, M.X. and Williamson, D.P. A general   approximation technique for constrained forest problems",   SIAM Journal on Computing, 24(2), pp. 296{   317 (1995).   38. Ruiz, H.E.R. The capacitated minimum spanning tree   problem", Ph.D. Thesis, Universitat Politecnica de   Catalunya, BarcelonaTech (2013).   39. Chen, J. and Chen, S. Optimization of vehicle routing   problem with load balancing and time windows in distribution",   4th International Conference on Wireless   Communications, Networking and Mobile Computing   (2008). DOI: 10.1109/WiCom.2008.1527   40. Fallah, H., Didehvar, F., and Rahmati, F. Approximation   algorithms for the load-balanced capacitated   vehicle routing problem", Bulletin of the Iranian   Mathematical Society (2020). DOI: 10.1007/s41980-   020-00440-3   41. Cowell, F.A. Measurement of inequality", In Handbook   of Income Distribution, A.B. Atkinson, and F.   Bourguignon, Ed., North Holland, Amsterdam (2000).   42. Garey, M.R. and Johnson, D.S. Computers and intractability:   a guide to the theory of NP-completeness"   Freeman, W.H. and Co. subs. of scienti_c American,   New York, United States, 338 pages (1979).   43. Papadimitriou, C.H. The Complexity of the capacitated   tree problem", Networks, 8, pp. 217{230 (1978).   44. Camerini, P.M., Galbiatai, G., and Ma_oli, F. Complexity   of spanning tree problems: part 1", European   Journal of Operational Research, 5, pp. 346{352   (1980).   45. Camerini, P.M., Ma_oli, F., Martello, S., et al. Most   and least uniform spanning trees", Discrete Applied   Mathematics, 15, pp. 181{187 (1986).   46. Beasley, J. Route _rst-cluster second methods for   vehicle routing", Omega, 11, pp. 403{408 (1983).   47. Haimovich, M. and Rinnooy Kan, A.H.G. Bounds and   heuristics for capacitated routing problems", Mathematics   of Operations Research, 10, pp. 527{524 (1985).   1492 H. Fallah et al./Scientia Iranica, Transactions D: Computer Science & ... 28 (2021) 1479{1492   48. Khachay, M. and Dubinin, R. PTAS for the Euclidean   capacitated vehicle routing problem in Rd", International   Conference on Discrete Optimization and Operations   Research, Lecture Notes in Computer Science   9869, pp. 193{205 (2016).