Frank R. Libsch, S.C. Lien
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.
Frank R. Libsch, S.C. Lien
IBM J. Res. Dev
Yigal Hoffner, Simon Field, et al.
EDOC 2004
Raymond F. Boyce, Donald D. Chamberlin, et al.
CACM
Ehud Altman, Kenneth R. Brown, et al.
PRX Quantum