Capacitated Network Design Problems: Hardness, Approximation Algorithms, and Connections to Group Steiner Tree

We design combinatorial approximation algorithms for the Capacitated Steiner Network (Cap-SN) problem and the Capaci-tated Multicommodity Flow (Cap-MCF) problem. These two prob-lems entail satisfying connectivity requirements when edges have costs and hard capacities. In Cap-SN, the flow has to be supported separately for each commodity while in Cap-MCF, the flow has to be sent simulta-neously for all commodities. We show that the Group Steiner problem on trees ([12]) is a special case of both problems. This implies the first poly-logarithmic lower bound for these problems by [17]. We then give various approximations to special cases of the problems. We generalize the well known Source location problem (see for example [19]), to a natural prob-lem called the Connected Rent or Buy Source Location problem. We show that this problem is a a simplification of Cap-SN and Cap-MCF and a generalization of Group Steiner on general graphs. We use Group Steiner Tree techniques, and more sophisticated techniques, to de