Survivable Network Activation Problems

In the Survivable Networks Activation problem we are given a graph G = (V, E), S subset of V, a family {f(uv) (x(u), x(v)) : uv is an element of E} of monotone non-decreasing activating functions from R-+(2) to {0, 1} each, and connectivity requirements {r(u, v) : u, v is an element of V}. The goal is to find a weight assignment w = {w(v) : v is an element of V} of minimum total weight w(V) = Sigma(v is an element of V) w(v), such that: for all u, v is an element of V, the activated graph G(w) = (V, E-w), where E-w = {uv : f(uv) (w(u), w(v)) = 1}, contains r(u, v) pairwise edge-disjoint uv-paths such that no two of them have a node in S\{u, v} in common. This problem was suggested recently by Panigrahi [12], generalizing the Node-Weighted Survivable Network and the Minimum-Power Survivable Network problems, as well as several other problems with motivation in wireless networks. We give new approximation algorithms for this problem. For undirected/directed graphs, our ratios are O(k log n) for k-Out/Inconnected Subgraph Activation and k-Connected Subgraph Activation. For directed graphs this solves a question from [12] for k = 1, while for the min-power case and k arbitrary this solves an open question from [9]. For other versions on undirected graphs, our ratios match the best known ones for the Node-Weighted Survivable Network problem [8].