Tight Guarantees for Cut-Relative Survivable Network Design via a Decomposition Technique

Nikhil Kumar, JJ Nan, Chaitanya Swamy

In the classical \emph{survivable-network-design problem} (SNDP), we are given an undirected graph $G=(V,E)$, non-negative edge costs, and some $(s_i,t_i,r_i)$ tuples, where $s_…