Approximation algorithms for minimum tree partition

AbstractWe consider a problem of locating communication centers. In this problem, it is required to partition the set of n customers into subsets minimizing the length of nets required to connect all the customers to the communication centers. Suppose that communication centers are to be placed in p of the customers locations. The number of customers each center supports is also given. The problem remains to divide a graph into sets of the given sizes, keeping the sum of the spanning trees minimal. The problem is NP-complete, and no polynomial algorithm with bounded error ratio can be given, unless P = NP. We present an approximation algorithm for the problem assuming that the edge lengths satisfy the triangle inequality. It runs in O(p24p + n2) time (n = ¦V¦) and comes within a factor of 2p− 1 of optimal. When the sets' sizes are all equal this algorithm runs in O(n2) time. Next, an improved algorithm is presented which obtains as an input a positive integer x (x⩽n − p) and runs in O(f(p,x)n2) time, where f is an exponential function of p and x, and comes within a factor of 2 +(2p−3)x of optimal. When the sets' sizes are all equal it runs in O(2(p+x)n2) time. A special algorithm is presented for the case p = 2