Date Added: Oct 2009
This paper discusses online and stochastic network design while taking into consideration the edge-connectivity survivable network design problem where a graph with edge costs and edge-connectivity requirements for different sets of vertices finds a minimum-cost network that provides the required connectivity. This problem has been known to admit good approximation algorithms in the offline case. But no algorithms have been derived for this problem in the online setting. With this paper, the authors provide a randomized O(rmax log3 n) competitive online algorithm. This algorithm works for the edge-connectivity network design problem where rmax = maxij rij. These algorithms employ standard embeddings of graphs into random subtrees. For instance, into singly connected sub-graphs. This is done as an intermediate step so that one receives algorithms for higher connectivity. The results of this paper for the online problem come up with approximation algorithms that admit strict cost-shares. This is available with the same strictness value and implies approximation algorithms for the rent-or-buy version as well as the stochastic version of the edge-connected network design problem with independent arrivals. The paper further discusses these two problems in detail for cases where the underlying graph is complete and edge-costs are metric. The paper further provides results to give O(1)-strict cost shares that provide constant-factor rent-or-buy and stochastic algorithms in these cases.