@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 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.},
keywords = {Capacitated Minimum Spanning Tree Problem,Load balancing,Approximation Algorithms,PTAS},
url = {http://scientiairanica.sharif.edu/article_22044.html},
eprint = {http://scientiairanica.sharif.edu/article_22044_172844d97d2bbd018bfc3773ff00991f.pdf}
}