Additive Approximation for Bounded Degree Survivable Network Design

We study a general network design problem with additional degree constraints. Given connectivity requirements ruv for all pairs of vertices, a Steiner network is a graph in which there are at least ruv edge-disjoint paths between u and v for all pairs of vertices u, v. In the MINIMUM BOUNDED-DEGREE STEINER NETWORK problem, we are given an undirected graph G with an edge cost for each edge, a connectivity requirement ruv for each pair of vertices u and v, and a degree upper bound for each vertex v. The task is to find a minimum cost Steiner network which satisfies all the degree upper bounds. The aim of this paper is to design approximation algorithms that minimize the total cost and the degree violation simultaneously. Our main results are the following: • There is a polynomial time algorithm which returns a Steiner forest of cost at most 2OPT and the degree violation at each vertex is at most 3, where OPT is the cost of an optimal solution which satisfies all the degree bounds. • There is a polynomial time algorithm which returns a Steiner network of cost at most 2OPT and the degree violation at each vertex is at most 6rmax + 3, where OPT is the cost of an optimal solution which satisfies all the degree bounds, and rmax := maxu,v{ruv}. These results achieve the best known guarantees for both the total cost and the degree violation simultaneously. As corollaries, these results provide the first additive approximation algorithms for finding low degree subgraphs including Steiner forests, k-edgeconnected subgraphs, and Steiner networks. The algorithms develop on the iterative relaxation method applied to a natural linear programming relaxation as in [10, 16, 22]. The new algorithms avoid paying a multiplicative factor of two on the degree bounds even though the algorithm can only pick edges with fractional value 1/2. This is based on a stronger characterization of the basic solutions of the linear programming relaxation. The analysis of the algorithm is nearly tight.