Placement of multimedia blocks on zoned disks
Renu Tewari, Richard P. King, et al.
IS&T/SPIE Electronic Imaging 1996
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.
Renu Tewari, Richard P. King, et al.
IS&T/SPIE Electronic Imaging 1996
M.J. Slattery, Joan L. Mitchell
IBM J. Res. Dev
Hang-Yip Liu, Steffen Schulze, et al.
Proceedings of SPIE - The International Society for Optical Engineering
Liat Ein-Dor, Y. Goldschmidt, et al.
IBM J. Res. Dev