A unified algorithm for degree bounded survivable network design (Q896300): Difference between revisions

This paper considers the minimum bounded degree Steiner network problem, where an undirected graph \(G\), a cost \(c_e\) on each edge \(e\), a degree bound \(b_v\) on each vertex \(v\) and a connectivity requirement \(r_{uv}\) for each pair of vertices \((u,v)\) are given and the objective is to find a Steiner network \(H \subseteq G\) with minimum total cost respecting the given degree bounds on the vertices. For this problem, a polynomial-time approximation algorithm with cost at most two times the optimal value is given such that the degree on each vertex is at most equal to \(\min \{ b_v + 3 r_{\max}, 2 b_v + 2 \}\), where \(r_{\max}\) is the maximum connectivity requirement. This improves a previous result for this problem given by the first author and \textit{M. Singh} [SIAM J. Comput. 42, No. 6, 2217--2242 (2013; Zbl 1285.68216)]. The authors give also an example for which their algorithm fails to give a \(2\)-approximation algorithm with a degree on each vertex at most \(b_v + 2\) for the minimum bounded degree Steiner forest problem.