APPROXIMATION ALGORITHMS FOR MINIMUM TREE PARTITION

We consider a problem of locating communication centers. In this probl em, it is required to partition the set of n customers into subsets mi nimizing the length of nets required to connect all the customers to t he 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 i nto sets of the given sizes, keeping the sum of the spanning trees min imal. The problem is NP-complete, and no polynomial algorithm with bou nded error ratio can be given, unless P=NP. We present an approximatio n algorithm for the problem assuming that the edge lengths satisfy the triangle inequality. It runs in O(p(2)4(p) + n(2)) 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 algorit hm is presented which obtains as an input a positive integer x (x less than or equal to n - p) and runs in O(f(p,x)n(2)) 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))n(2)) time. A special algorithm is presented for the case p = 2. (C) 1998 Elsevier Science B.V. All rights reserved.