A Polylogarithmic Approximation for Buy-at-Bulk Network Design with Protection

We consider Buy-at-Bulk Network Design with Protection, which is motivated by fault-tolerance in high speed (optical) networks. Given a graph G=(V,E) and a set of demand pairs (s1,t1), …,(sr,tr), the goal is to route a demand of δ(i) for each pair (si,ti) along two internally vertex-disjoint paths (to protect against a vertex failure) so as to minimize the total cost of routing. The cost of the routing is ∑e fe(xe), where xe is the total flow on edge e and fe: ℝ+ → ℝ+ is a sub-additive cost function that models economies of scale for installing capacity on e. We obtain a polylogarithmic approximation for this problem. The algorithm is based on connections and insights from length-constrained network design. Along the way, we obtain a bicriteria approximation algorithm for a 2-vertex connected length-constrained problem, which is of independent interest.