Approximability of Capacitated Network Design.

link: http://arxiv.org/abs/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
$o(m)$ approximation, where $m$ is the number of edges in the graph. In this
paper, we obtain several new results and insights into the approximability of
Cap-SNDP.