an approximation algorithm for the balanced capacitated minimum spanning tree problem

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.