Degree Bounded Survivable Network Design

• INSTANCE: Graph $G=(V,E)$ , edge costs $c : E \rightarrow {\mathbb{R}}_+$ , degree bounds $b_v,v\in V$ , requirements $r_{uv},u,v\in V$

• SOLUTION: A subgraph $H$ of $G$ which contains for each pair of vertices $u,v$ at least $r_{uv}$ edge-disjoint paths from $u$ to $v$ and such that for all $v\in V$ , $d_H(v)\leq b_v$

• COST FUNCTION: $c(H)$

• OBJECTIVE: Minimize.

• Approx.: There exists an algorithm which constructs a subgraph $H$ of cost at most $2$ times the optimum cost such that $H$ satisfies all the connectivity requirements $r_{uv}$ and such that $d_H(v)\leq \min\{b_v+3r_{\max},2b_v+2\}$ , where $r_{\max}=\max_{u,v}r_{uv}$ [82].
• Comment: There exists a $(O(1),O(1))$ bicriteria approximation algorithm for Degree Bounded Survivable Network Design with element-connectivity requirements, where the paths satisfying the connectivity requirements have to be element disjoint [45]. For the Degree Bounded Survivable Network Design problem with node-connectivity requirements, there exists a $(O(k^3 \log n),O(k^3 \log n))$ bicriteria approximation algorithm, where $k$ is the maximum connectivity requirement of any pair [45].