Online and stochastic survivable network design

ABSTRACT

Consider the edge-connectivity survivable network design problem: given a graph G = (V,E) with edge-costs, and edge-connectivity requirements r_ij for every pair of vertices i,j, 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 O(r_max log³ n) competitive online algorithm for this edge-connectivity network design problem, 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.

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-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.

REFERENCES

• 1: Ittai Abraham , Yair Bartal , Ofer Neiman, Nearly Tight Low Stretch Spanning Trees, Proceedings of the 2008 49th Annual IEEE Symposium on Foundations of Computer Science, p.781-790, October 25-28, 2008 [doi>10.1109/FOCS.2008.62]
• 2: Ajit Agrawal , Philip Klein , R. Ravi, When Trees Collide: An Approximation Algorithm for theGeneralized Steiner Problem on Networks, SIAM Journal on Computing, v.24 n.3, p.440-456, June 1995 [doi>10.1137/S0097539792236237]
• 3: Noga Alon , Baruch Awerbuch , Yossi Azar, The online set cover problem, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA [doi>10.1145/780542.780558]
• 4: Noga Alon , Baruch Awerbuch , Yossi Azar , Niv Buchbinder , Joseph (Seffi) Naor, A general approach to online network optimization problems, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
• 5: Baruch Awerbuch , Yossi Azar , Yair Bartal, On-line generalized Steiner problem, Theoretical Computer Science, v.324 n.2-3, p.313-324, 20 September 2004 [doi>10.1016/j.tcs.2004.05.021]
• 6: Nikhil Bansal , Rohit Khandekar , Viswanath Nagarajan, Additive guarantees for degree bounded directed network design, Proceedings of the 40th annual ACM symposium on Theory of computing, May 17-20, 2008, Victoria, British Columbia, Canada [doi>10.1145/1374376.1374486]
• 7: Y. Bartal, Probabilistic approximation of metric spaces and its algorithmic applications, Proceedings of the 37th Annual Symposium on Foundations of Computer Science, p.184, October 14-16, 1996
• 8: Piotr Berman , Chris Coulston, On-line algorithms for Steiner tree problems (extended abstract), Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.344-353, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258618]
• 9: Niv Buchbinder , Joseph (Seffit) Naor, Improved Bounds for Online Routing and Packing Via a Primal-Dual Approach, Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science, p.293-304, October 21-24, 2006 [doi>10.1109/FOCS.2006.39]
• 10: Tanmoy Chakraborty , Julia Chuzhoy , Sanjeev Khanna, Network design for vertex connectivity, Proceedings of the 40th annual ACM symposium on Theory of computing, May 17-20, 2008, Victoria, British Columbia, Canada [doi>10.1145/1374376.1374403]
• 11: Yuk Hei Chan , Wai Shing Fung , Lap Chi Lau , Chun Kong Yung, Degree Bounded Network Design with Metric Costs, Proceedings of the 2008 49th Annual IEEE Symposium on Foundations of Computer Science, p.125-134, October 25-28, 2008 [doi>10.1109/FOCS.2008.28]
• 12: C. Chekuri, A. Gupta, N. Korula, R. Krishnaswamy, A. Kumar. Cost-sharing for subgraph k-edge-connectivity, 2008. Unpublished.
• 13: C. Chekuri, N. Korula. Single-sink network design with vertex connectivity requirements. In FST&#;TCS. 2008.
• 14: J. Cheriyan, S. Vempala, A. Vetta. An approximation algorithm for the minimum-cost k -vertex connected subgraph. SIAM J. Comput. , 32(4):1050--1055 (electronic), 2003.
• 15: Joseph Cheriyan , Adrian Vetta, Approximation algorithms for network design with metric costs, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA [doi>10.1145/1060590.1060616]
• 16: Julia Chuzhoy , Sanjeev Khanna, Algorithms for Single-Source Vertex Connectivity, Proceedings of the 2008 49th Annual IEEE Symposium on Foundations of Computer Science, p.105-114, October 25-28, 2008 [doi>10.1109/FOCS.2008.63]
• 17: Michael Elkin , Yuval Emek , Daniel A. Spielman , Shang-Hua Teng, Lower-stretch spanning trees, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA [doi>10.1145/1060590.1060665]
• 18: Jittat Fakcharoenphol , Bundit Laekhanukit, An o(log² k)-approximation algorithm for the k-vertex connected spanning subgraph problem, Proceedings of the 40th annual ACM symposium on Theory of computing, May 17-20, 2008, Victoria, British Columbia, Canada [doi>10.1145/1374376.1374401]
• 19: Jittat Fakcharoenphol , Satish Rao , Kunal Talwar, A tight bound on approximating arbitrary metrics by tree metrics, Journal of Computer and System Sciences, v.69 n.3, p.485-497, November 2004 [doi>10.1016/j.jcss.2004.04.011]
• 20: Lisa Fleischer , Kamal Jain , David P. Williamson, Iterative rounding 2-approximation algorithms for minimum-cost vertex connectivity problems, Journal of Computer and System Sciences, v.72 n.5, p.838-867, August 2006 [doi>10.1016/j.jcss.2005.05.006]
• 21: Lisa Fleischer , Jochen Könemann , Stefano Leonardi , Guido Schäfer, Simple cost sharing schemes for multicommodity rent-or-buy and stochastic Steiner tree, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA [doi>10.1145/1132516.1132609]
• 22: M. X. Goemans , A. V. Goldberg , S. Plotkin , D. B. Shmoys , É. Tardos , D. P. Williamson, Improved approximation algorithms for network design problems, Proceedings of the fifth annual ACM-SIAM symposium on Discrete algorithms, p.223-232, January 23-25, 1994, Arlington, Virginia, United States
• 23: Michel X. Goemans , David P. Williamson, A General Approximation Technique for Constrained Forest Problems, SIAM Journal on Computing, v.24 n.2, p.296-317, April 1995 [doi>10.1137/S0097539793242618]
• 24: Anupam Gupta , Amit Kumar , Martin P´al , Tim Roughgarden, Approximation via cost sharing: Simpler and better approximation algorithms for network design, Journal of the ACM (JACM), v.54 n.3, p.11-es, June 2007 [doi>10.1145/1236457.1236458]
• 25: Anupam Gupta , Martin Pál , R. Ravi , Amitabh Sinha, Boosted sampling: approximation algorithms for stochastic optimization, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA [doi>10.1145/1007352.1007419]
• 26: M. Imase, B. M. Waxman. Dynamic Steiner tree problem. SIAM J. Discrete Math., 4(3):369--384, 1991.
• 27: Nicole Immorlica , David Karger , Maria Minkoff , Vahab S. Mirrokni, On the costs and benefits of procrastination: approximation algorithms for stochastic combinatorial optimization problems, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
• 28: Kamal Jain, A Factor 2 Approximation Algorithm for the Generalized Steiner Network Problem, Proceedings of the 39th Annual Symposium on Foundations of Computer Science, p.448, November 08-11, 1998
• 29: Samir Khuller , Balaji Raghavachari, Improved approximation algorithms for uniform connectivity problems, Journal of Algorithms, v.21 n.2, p.434-450, Sept. 1996 [doi>10.1006/jagm.1996.0052]
• 30: P. N. Klein, R. Ravi. When cycles collapse: A general approximation technique for constrained two-connectivity problems. In 3rd IPCO, 39--56. 1993.
• 31: Guy Kortsarz , Robert Krauthgamer , James R. Lee, Hardness of Approximation for Vertex-Connectivity Network Design Problems, SIAM Journal on Computing, v.33 n.3, p.704-720, 2004 [doi>10.1137/S0097539702416736]
• 32: G. Kortsarz, Z. Nutov. Approximating node connectivity problems via set covers. Algorithmica , 37(2):75--92, 2003.
• 33: Lap Chi Lau , Joseph (Seffi) Naor , Mohammad R. Salavatipour , Mohit Singh, Survivable network design with degree or order constraints, Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, June 11-13, 2007, San Diego, California, USA [doi>10.1145/1250790.1250886]
• 34: Lap Chi Lau , Mohit Singh, Additive approximation for bounded degree survivable network design, Proceedings of the 40th annual ACM symposium on Theory of computing, May 17-20, 2008, Victoria, British Columbia, Canada [doi>10.1145/1374376.1374485]
• 35: R. Ravi, A. Sinha. Hedging uncertainty: Approximation algorithms for stochastic optimization problems. In 10th IPCO, 101--115. 2004.
• 36: David B. Shmoys , Chaitanya Swamy, An approximation scheme for stochastic linear programming and its application to stochastic integer programs, Journal of the ACM (JACM), v.53 n.6, p.978-1012, November 2006 [doi>10.1145/1217856.1217860]
• 37: David P. Williamson , Michel X. Goemans , Milena Mihail , Vijay V. Vazirani, A primal-dual approximation algorithm for generalized Steiner network problems, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.708-717, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167268]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems

General Terms:
Algorithms, Theory

Keywords:
approximation algorithms, network design problems, online algorithms