Sharif University of TechnologyScientia Iranica1026-309828Special issue on collective behavior of nonlinear dynamical networks20210601An approximation algorithm for the balanced capacitated minimum spanning tree problem147914922204410.24200/sci.2020.54242.3663ENH.FallahDepartment of Mathematics and Computer Science, Amirkabir University of Technology, Tehran, P.O. Box 15875-4413, IranF.DidehvarDepartment of Mathematics and Computer Science, Amirkabir University of Technology, Tehran, P.O. Box 15875-4413, IranF.RahmatiDepartment of Mathematics and Computer Science, Amirkabir University of Technology, Tehran, P.O. Box 15875-4413, IranJournal Article20190827The capacitated minimum spanning tree problem (CMSTP), a well-known combinatorial optimiza-<br />tion problem, holds a central place in telecommunication network design. This problem is to find a minimum<br />cost spanning tree with an extra cardinality limitation on the orders of the subtrees incident to a certain root<br />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,<br />in this paper.<br />Considering the maximum order of the subtrees Q, we provide a (3 - 1<br />/Q)-approximation algorithm to find a<br />balanced solution. We improve this result to a (2:5 + epsilon)-approximation algorithm (for every given epsilon > 0), in<br />the 2d-Euclidean spaces. Also, we present a polynomial time approximation scheme (PTAS) for CMSTP.http://scientiairanica.sharif.edu/article_22044_172844d97d2bbd018bfc3773ff00991f.pdf