Approximation algorithms for a capacitated network design problem

Abstract. We study a network loading problem with applications in lo-cal access network design. Given a network, the problem is to route ow from several sources to a sink and to install capacity on the edges to sup-port ows at minimum cost. Capacity can be purchased only in multiples of a xed quantity. All the ow from a source must be routed in a sin-gle path to the sink. This NP-hard problem generalizes the Steiner tree problem and also more eectively models the applications traditionally formulated as capacitated tree problems. We present an approximation algorithm with performance ratio ( ST +2) where ST is the performance ratio of any approximation algorithm for minimum Steiner tree. When all sources have the same demand value, the ratio improves to ( ST +1) and in particular, to 2 when all nodes in the graph are sources.