Global routing revisited
Michael D. Moffitt
ICCAD 2009
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.
Michael D. Moffitt
ICCAD 2009
Fan Zhang, Junwei Cao, et al.
IEEE TETC
Erich P. Stuntebeck, John S. Davis II, et al.
HotMobile 2008
Ohad Shamir, Sivan Sabato, et al.
Theoretical Computer Science