Additive guarantees for degree bounded directed network design

We present polynomial-time approximation algorithms for some degree-bounded directed network design problems. Our main result is for intersecting supermodular connectivity with degree bounds: given a directed graph G=(V,E) with non-negative edge-costs, a connectivity requirement specified by an intersecting supermodular function f, and upper bounds av, bvv¿ V on in-degrees and out-degrees of vertices, find a minimum-cost f-connected subgraph of G that satisfies the degree bounds. We give a bicriteria approximation algorithm that for any 0 = e = 1/2, computes an f-connected subgraph with in-degrees at most ¿ av/1-e ¿ + 4, out-degrees at most ¿ bv/1-e ¿ + 4, and cost at most 1/e times the optimum. This includes, as a special case, the minimum-cost degree-bounded arborescence problem. We also obtain similar results for the (more general) class of crossing supermodular requirements. Our result extends and improves the (3av+4, 3bv+4, 3)-approximation of Lau et al. Setting e=0, our result gives the first purely additive guarantee for the unweighted versions of these problems. Our algorithm is based on rounding an LP relaxation for the problem. We also prove that the above cost-degree trade-off (even for the degree-bounded arborescence problem) is optimal relative to the natural LP relaxation. For every