Simple cost sharing schemes for multicommodity rent-or-buy and stochastic Steiner tree

ABSTRACT

In the multi-commodity rent-or-buy network design problem (MRoB) we are given a network together with a set of k terminal pairs R = (s_1, t_1), ..., (s_k, t_k). The goal is to install capacities on the edges of the network so that a prescribed amount of flow f_i can be routed between all terminal pairs s_i and t_i simultaneously. We can either rent capacity on an edge at some cost per unit flow or buy infinite capacity on an edge at some larger fixed cost. The overall objective is to install capacities at a minimum total cost.The version of the stochastic Steiner tree problem (SST) considered here is the Steiner tree problem in the model of two-stage stochastic optimization with recourse. In stage one, there is a known probability distribution on subsets of vertices and we can choose to buy a subset of edges at a given cost. In stage two, a subset of vertices T from the prior known distribution is realized, and additional edges can be bought at a possibly higher cost. The objective is to buy a set of edges in stages one and two so that all vertices in T are connected, and the expected cost is minimized.Gupta et al. (FOCS '03) give a randomized scheme for the MRoB problem that was both used subsequently to improve the approximation ratio for this problem, and extended to yield the best approximation algorithm for SST. One building block of this scheme is a good approximation algorithm for Steiner forests.We present a surprisingly simple 5-approximation algorithm for MRoB and 6-approximation for SST, improving on the best previous guarantees of 6.828 and 12.6, and show that no approximation ratio better than 4.67 can be achieved using the above mentioned randomized scheme in combination with the currently best known Steiner forest approximation algorithms. A key component of our approach are cost shares that are 3-strict for the unmodified primal-dual Steiner forest algorithm.

REFERENCES

• 1: Matthew Andrews, Hardness of Buy-at-Bulk Network Design, Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science (FOCS'04), p.115-124, October 17-19, 2004 [doi>10.1109/FOCS.2004.32]
• 2: B. Awerbuch , Y. Azar, Buy-at-bulk network design, Proceedings of the 38th Annual Symposium on Foundations of Computer Science (FOCS '97), p.542, October 19-22, 1997
• 3: 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]
• 4: 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
• 5: Yair Bartal, On approximating arbitrary metrices by tree metrics, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.161-168, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276725]
• 6: Luca Becchetti , Jochen Könemann , Stefano Leonardi , M. Pál, Sharing the cost more efficiently: improved approximation for multicommodity rent-or-buy, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
• 7: Marshall Bern , Paul Plassmann, The steiner problem with edge lengths 1 and 2,, Information Processing Letters, v.32 n.4, p.171-176, Sept 1, 1989 [doi>10.1016/0020-0190(89)90039-2]
• 8: Jittat Fakcharoenphol , Satish Rao , Kunal Talwar, A tight bound on approximating arbitrary metrics by tree metrics, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA [doi>10.1145/780542.780608]
• 9: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 10: Anupam Gupta , Amit Kumar , Martin Pál , Tim Roughgarden, Approximation Via Cost-Sharing: A Simple Approximation Algorithm for the Multicommodity Rent-or-Buy Problem, Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, p.606, October 11-14, 2003
• 11: Anupam Gupta , Amit Kumar , Tim Roughgarden, Simpler and better approximation algorithms for network design, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA [doi>10.1145/780542.780597]
• 12: A. Gupta and M. Pál. Stochastic Steiner trees without a root. In Proceedings, International Colloquium on Automata, Languages and Programming, pages 1051--1063, 2005.
• 13: 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]
• 14: Anupam Gupta , R. Ravi , Amitabh Sinha, An Edge in Time Saves Nine: LP Rounding Approximation Algorithms for Stochastic Network Design, Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science (FOCS'04), p.218-227, October 17-19, 2004 [doi>10.1109/FOCS.2004.11]
• 15: 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]
• 16: Amit Kumar , Anupam Gupta , Tim Roughgarden, A Constant-Factor Approximation Algorithm for the Multicommodity, Proceedings of the 43rd Symposium on Foundations of Computer Science, p.333, November 16-19, 2002

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, Design, Theory

Keywords:
approximation algorithms, cost sharing, stochastic optimization