Additive guarantees for degree bounded directed network design

Abstract

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, b v}v∈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 ≤ ε ≤ 1/2 computes an f-connected subgraph with in-degrees at most [av/1- ε] + 4, out-degrees at most [bv/1-ε] + 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. [13]. Setting ε = 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 0 < ε < 1, we show an instance where any arborescence with out-degrees at most b v/1-ε+ O(1) has cost at least 1-o(1)/ε times the optimal LP value. For the special case of finding a minimum degree arborescence (without costs), we give a stronger +2 additive, approximation. This improves on a result of Lau et al. [13] that gives a, 2δ* + 2 guarantee, and Klein et al. [11] that gives a (1 + ε)δ* + O(log1+ε n) bound, where δ* is the degree of the optimal arborescence. As a corollary of our result, we (almost) settle a conjecture of Bang-Jensen et al. [1] on low-degree arborescences. Our algorithms use the iterative rounding technique of Jain [9], which was used by Lau et al. [13] and Singh and Lau [19] in the context of degree-bounded network design. It is however non-trivial to extend these techniques to the directed setting without incurring a multiplicative violation in the degree bounds. This is due to the fact that known polyhedral characterization of arborescences has the cut-constraints which, along with degree-constraints, are unsuitable for arguing the existence of integral variables in a basic feasible solution. We overcome this difficulty by enhancing the iterative rounding steps and by means of stronger counting arguments. Our counting technique is quite general, and it also simplifies the proofs of many previous results. We also apply the technique to undirected graphs. We consider the minimum crossing spanning tree, problem: given an undirected edge-weighted graph G, edge-subsets {Ei}iκ=1, and non-negative integers {bi}iκ=1, find a minimum-cost spanning tree (if it exists) in G that contains at most bi edges from each set Ei. We obtain a +(r- 1) additive approximation for this problem, when each edge lies in at most r sets; this considerably improves the result of Bilò et al. [2]. A special case of this problem is degree-bounded minimum spanning tree, and our result gives a substantially easier proof of the recent +1 approximation of Singh and Lau [19]. Copyright 2008 ACM.