Iterative rounding approximation algorithms for degree-bounded node-connectivity network design

We consider the problem of finding a minimum edge cost subgraph of a graph satisfying both given node-connectivity requirements and degree upper bounds on nodes. We present an iterative rounding algorithm of the biset linear programming relaxation for this problem. For directed graphs and k-out-connectivity requirements from a root, our algorithm computes a solution that is a 2-approximation on the cost, and the degree of each node v in the solution is at most 2b(ρ) + O(k), where b(ρ) is the degree upper bound on v. For undirected graphs and elementconnectivity requirements with maximum connectivity requirement k, our algorithm computes a solution that is a 4-approximation on the cost, and the degree of each node v in the solution is at most 4b(ρ) + O(k). These ratios improve the previous O(log k)-approximation on the cost and O(2^kb(ρ))-approximation on the degrees. Our algorithms can be used to improve approximation ratios for other node-connectivity problems such as undirected k-out-connectivity, directed and undirected k-connectivity, and undirected rooted k-connectivity and subset k-connectivity.