TY - GEN

T1 - Online and stochastic survivable network design

AU - Gupta, Anupam

AU - Krishnaswamy, Ravishankar

AU - Ravi, R.

PY - 2009

Y1 - 2009

N2 - Consider the edge-connectivity survivable network design problem: 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 net- work 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 O(rmax log 3 n) competitive online algorithm for this edge-connectivity network design problem, where rmax = maxij rij. Our algorithms use the standard embeddings of graphs into random subtrees (i.e., into singly connected sub- graphs) as an intermediate step to get algorithms for higher connectivity. Our results for the online problem give us approxima- tion algorithms that admit strict cost-shares with the same strictness value. This, in turn, implies approximation al-gorithms for (a) the rent-or-buy version and (b) the (two- stage) stochastic version of the edge-connected network design problem with independent arrivals. For these two problems, if we are in the case when the underlying graph is complete and the edge-costs are metric (i.e., satisfy the triangle inequality), we improve our results to give O(1)-strict cost shares, which gives constant-factor rent-or-buy and stochastic algorithms for these instances.

AB - Consider the edge-connectivity survivable network design problem: 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 net- work 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 O(rmax log 3 n) competitive online algorithm for this edge-connectivity network design problem, where rmax = maxij rij. Our algorithms use the standard embeddings of graphs into random subtrees (i.e., into singly connected sub- graphs) as an intermediate step to get algorithms for higher connectivity. Our results for the online problem give us approxima- tion algorithms that admit strict cost-shares with the same strictness value. This, in turn, implies approximation al-gorithms for (a) the rent-or-buy version and (b) the (two- stage) stochastic version of the edge-connected network design problem with independent arrivals. For these two problems, if we are in the case when the underlying graph is complete and the edge-costs are metric (i.e., satisfy the triangle inequality), we improve our results to give O(1)-strict cost shares, which gives constant-factor rent-or-buy and stochastic algorithms for these instances.

KW - Approximation Algorithms

KW - Network Design Problems

KW - Online Algorithms

UR - http://www.scopus.com/inward/record.url?scp=70350643835&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=70350643835&partnerID=8YFLogxK

U2 - 10.1145/1536414.1536507

DO - 10.1145/1536414.1536507

M3 - Conference contribution

AN - SCOPUS:70350643835

SN - 9781605585062

T3 - Proceedings of the Annual ACM Symposium on Theory of Computing

SP - 685

EP - 694

BT - STOC'09 - Proceedings of the 2009 ACM International Symposium on Theory of Computing

T2 - 41st Annual ACM Symposium on Theory of Computing, STOC '09

Y2 - 31 May 2009 through 2 June 2009

ER -