Approximability of Capacitated Network Design
arXiv:1009.5734
Abstract
In the {\em capacitated} survivable network design problem (Cap-SNDP), we are given an undirected multi-graph where each edge has a capacity and a cost. The goal is to find a minimum cost subset of edges that satisfies a given set of pairwise minimum-cut requirements. Unlike its classical special case of SNDP when all capacities are unit, the approximability of Cap-SNDP is not well understood; even in very restricted settings no known algorithm achieves a approximation, where is the number of edges in the graph. In this paper, we obtain several new results and insights into the approximability of Cap-SNDP.
19 pages, 1 figure