Rolf Clauberg
IBM J. Res. Dev
In the survivable network design problem (SNDP), the goal is to find a minimum-cost spanning subgraph satisfying certain connectivity requirements. We study the vertex-connectivity variant of SNDP in which the input specifies, for each pair of vertices, a required number of vertex-disjoint paths connecting them. We give the first strong lower bound on the approximability of SNDP, showing that the problem admits no efficient 2 log1-εn ratio approximation for any fixed ε > 0, unless NP ⊆ DTIME(n polylog(n)). We show hardness of approximation results for some important special cases of SNDP, and we exhibit the first lower bound on the approximability of the related classical NP-hard problem of augmenting the connectivity of a graph using edges from a given set.
Rolf Clauberg
IBM J. Res. Dev
Bowen Zhou, Bing Xiang, et al.
SSST 2008
Maciel Zortea, Miguel Paredes, et al.
IGARSS 2021
Heinz Koeppl, Marc Hafner, et al.
BMC Bioinformatics