Approximation Algorithms for the Capacitated Minimum Spanning Tree Problem and its Variants in Network Design

Given an undirected graph G = (V, E) with nonnegative costs on its edges, a root node r is an element of V, a set of demands D subset of V with demand v is an element of D wishing to route w(v) units of flow (weight) to r, and a positive number k, the Capacitated Minimum Steiner Tree (CMStT) problem asks for a minimum Steiner tree, rooted at r, spanning the vertices in D boolean OR {r}, in which the sum of the vertex weights in every subtree connected to r is at most k. When D = V , this problem is known as the Capacitated Minimum Spanning Tree (CMST) problem. Both CMsT and CMST problems are NP-hard. In this article, we present approximation algorithms for these problems and several of their variants in network design. Our main results are the following: -We present a (gamma(rho ST)+2)-approximation algorithm for the CMStT problem, where y is the inverse Steiner ratio, and rho(ST) is the best achievable approximation ratio for the Steiner tree problem. Our ratio improves the current best ratio of 2(rho ST) + 2 for this problem. -In particular, we obtain (gamma +2)-approximation ratio for the CMST problem, which is an improvement over the current best ratio of 4 for this problem. For points in Euclidean and rectilinear planes, our result translates into ratios of 3.1548 and 3.5, respectively. -For instances in the plane, under the L-p norm, with the vertices in D having uniform weights, we present a nontrivial (7/5 rho(ST)+ 3/2 )-approximation algorithm for the CMStT problem. This translates into a ratio of 2.9 for the CMST problem with uniform vertex weights in the L-p metric plane. Our ratio of 2.9 solves the long-standing open problem of obtaining any ratio better than 3 for this case. -For the CMST problem, we show how to obtain a 2-approximation for graphs in metric spaces with unit vertex weights and k = 3, 4. -For the budgeted CMST problem, in which the weights of the subtrees connected to r could be up to k instead of k (alpha >= 1), we obtain a ratio of gamma+ 2/alpha.