@article { author = {Fallah, H. and Didehvar, F. and Rahmati, F.}, title = {An approximation algorithm for the balanced capacitated minimum spanning tree problem}, journal = {Scientia Iranica}, volume = {28}, number = {Special issue on collective behavior of nonlinear dynamical networks}, pages = {1479-1492}, year = {2021}, publisher = {Sharif University of Technology}, issn = {1026-3098}, eissn = {2345-3605}, doi = {10.24200/sci.2020.54242.3663}, abstract = {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 minimumcost spanning tree with an extra cardinality limitation on the orders of the subtrees incident to a certain rootnode. 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 abalanced solution. We improve this result to a (2:5 + \epsilon)-approximation algorithm (for every given \epsilon > 0), inthe 2d-Euclidean spaces. Also, we present a polynomial time approximation scheme (PTAS) for CMSTP.}, keywords = {Capacitated Minimum Spanning Tree Problem,Load balancing,Approximation Algorithms,PTAS}, url = {https://scientiairanica.sharif.edu/article_22044.html}, eprint = {https://scientiairanica.sharif.edu/article_22044_172844d97d2bbd018bfc3773ff00991f.pdf} }