Online and stochastic survivable network design

Anupam Gupta, Ravishankar Krishnaswamy, R. Ravi

Research output: Contribution to journalArticlepeer-review


Consider the edge-connectivity survivable network design problem (SNDP): given a graph G = (V, E) with edge-costs, and edge-connectivity requirements rij ∈ ℤ≥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 Õ(rmax log3 n)-competitive online algorithm for this edge-connectivity network design problem that runs in time O(mrmax), where r max = maxij rij. 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.

Original languageEnglish (US)
Pages (from-to)1649-1672
Number of pages24
JournalSIAM Journal on Computing
Issue number6
StatePublished - 2012


  • Approximation algorithms
  • Online algorithms
  • Stochastic optimization
  • Survivable network design

ASJC Scopus subject areas

  • General Computer Science
  • General Mathematics


Dive into the research topics of 'Online and stochastic survivable network design'. Together they form a unique fingerprint.

Cite this