%0 Journal Article
%T An approximation algorithm for the balanced capacitated minimum spanning tree problem
%J Scientia Iranica
%I Sharif University of Technology
%Z 1026-3098
%A Fallah, H.
%A Didehvar, F.
%A Rahmati, F.
%D 2021
%\ 06/01/2021
%V 28
%N Special issue on collective behavior of nonlinear dynamical networks
%P 1479-1492
%! An approximation algorithm for the balanced capacitated minimum spanning tree problem
%K Capacitated Minimum Spanning Tree Problem
%K Load balancing
%K Approximation Algorithms
%K PTAS
%R 10.24200/sci.2020.54242.3663
%X 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 find 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.
%U http://scientiairanica.sharif.edu/article_22044_172844d97d2bbd018bfc3773ff00991f.pdf