Survivable network design problems in wireless networks

Survivable network design is an important suite of algorithmic problems where the goal is to select a minimum cost network subject to the constraint that some desired connectivity property has to be satisfied by the network. Traditionally, these problems have been studied in a model where individual edges (and sometimes nodes) have an associated cost. This model does not faithfully represent wireless networks, where the activation of an edge is dependent on the selection of parameter values at its endpoints, and the cost incurred is a function of these values. We present a realistic optimization model for the design of survivable wireless networks that generalizes various connectivity problems studied in the theory literature, e.g. node-weighted steiner network, power optimization, minimum connected dominating set, and in the networking literature, e.g. installation cost optimization, minimum broadcast tree. We obtain the following algorithmic results for our general model:

1. For k = 1 and 2, we give O(log n)-approximation algorithms for both the vertex and edge connectivity versions of the k-connectivity problem. These results are tight (up to constants); we show that even for k = 1, it is NP-hard to obtain an approximation factor of o(log n).

2. For the minimum steiner network problem, we give a tight (up to constants) O(log n)-approximation algorithm.

3. We give a reduction from the k-edge connectivity problem to a more tractable degree-constrained problem. This involves proving new connectivity theorems that might be of independent interest. We apply this result to obtain new approximation algorithms in the power optimization and installation cost optimization applications.