Online and stochastic survivable network design

Consider the edge-connectivity survivable network design problem (SNDP): given a graph G = (V, E) with edge-costs, and edge-connectivity requirements r_ij ∈ ℤ_≥0 for every pair of vertices i, j ∈ V, find an (approximately) minimum-cost network that provides the required connectivity. While this problem is known to admit good approximation algorithms in the offline case, no algorithms were known for this problem in the online setting. In this paper, we give a randomized Õ(r_max log³ n)-competitive online algorithm for this edge-connectivity network design problem that runs in time O(m^rmax), where r _max = max_ij r_ij. Our algorithms use the standard embeddings of graphs into random subtrees (i.e., into singly connected subgraphs) as an intermediate step to get algorithms for higher connectivity. As a consequence of using these random embeddings, our algorithms are competitive only against oblivious adversaries. Our results for the online problem give us approximation algorithms that admit strict cost-shares with the same strictness value. This, in turn, implies approximation algorithms for (a) the rent-or-b uy version and (b) the (two-stage) stochastic version of the edge-connected network design problem with independent arrivals. If we are in the case when the underlying graph is complete and the edge-costs are metric (i.e., the triangle inequality is satisfied), we improve on our results to give an O(log n)-competitive deterministic online algorithm for the rooted version of the problem, and constant-factor approximation algorithms for the rent-or-buy and stochastic variants of SNDP.