Approximability of Capacitated Network Design

Computer Science – Data Structures and Algorithms

Scientific paper

Rate now

  [ 0.00 ] – not rated yet Voters 0   Comments 0


19 pages, 1 figure

Scientific paper

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.

No associations


Say what you really think

Search for scientists and scientific papers. Rate them and share your experience with other people.


Approximability of Capacitated Network Design does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Approximability of Capacitated Network Design, we encourage you to share that experience with our community. Your opinion is very important and Approximability of Capacitated Network Design will most certainly appreciate the feedback.

Rate now


Profile ID: LFWR-SCP-O-522319

All data on this website is collected from public sources. Our data reflects the most accurate information available at the time of publication.