LAUSR

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 minimum cost spanning tree with an extra cardinality limitation on the orders of the subtrees incident to a certain root 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, in this paper. Considering the maximum order of the subtrees Q, we provide a (3 - 1 /Q)-approximation algorithm to find a balanced solution. We improve this result to a (2:5 + epsilon)-approximation algorithm (for every given epsilon > 0), in the 2d-Euclidean spaces. Also, we present a polynomial time approximation scheme (PTAS) for CMSTP.