Survivable Network Activation Problems

In the

Survivable Networks Activation

problem we are given a graph

G

 = (

V

,

E

),

S

 ⊆ 

V

, a family {

f

uv

(

x

u

,

x

v

):

uv

 ∈ 

E

} of monotone non-decreasing

activating functions

from

$\mathbb{R}^2_+$

to {0,1} each, and

connectivity requirements

{

r

(

u

,

v

):

u

,

v

 ∈ 

V

}. The goal is to find a

weight assignment

w

 = {

w

v

:

v

 ∈ 

V

} of minimum total weight

w

(

V

) = ∑ 

v

 ∈ 

V

w

v

, such that: for all

u

,

v

 ∈ 

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/In-connected 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].