2010/09/29 by Deeparnab Chakrabarty, Chandra Chekuri, Chakrabarty, Deeparnab +5
Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #Optimization and Search Problems #cs.DM #cs.DS
paper · pdf · doi:10.48550/arxiv.1009.5734
19 pages, 1 figure
arxiv created 2010/09/29 · openalex publication_date 2010/09/29 · arxiv updated 2010/09/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.