A constant-factor approximation for stochastic Steiner forest

ABSTRACT

We consider the stochastic Steiner forest problem: suppose we were given a collection of Steiner forest instances, and were guaranteed that a random one of these instances would appear tomorrow; moreover, the cost of edges tomorrow will be λ times the cost of edges today. Which edges should we buy today so that we can extend it to a solution for the instance arriving tomorrow, to minimize the expected total cost? While very general results have been developed for many problems in stochastic discrete optimization over the past years, the approximation status of the stochastic Steiner Forest problem has remained open, with previous works yielding constant-factor approximations only for special cases. We resolve the status of this problem by giving a constant-factor primal-dual based approximation algorithm.

REFERENCES

• 1: 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]
• 2: Matthew Andrews, Hardness of Buy-at-Bulk Network Design, Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science, p.115-124, October 17-19, 2004 [doi>10.1109/FOCS.2004.32]
• 3: B. Awerbuch , Y. Azar, Buy-at-bulk network design, Proceedings of the 38th Annual Symposium on Foundations of Computer Science, p.542, October 19-22, 1997
• 4: M. Charikar, C. Chekuri, M. Pál. Sampling bounds for stochastic optimization. In 8th APPROX, LNCS, vol. 3624, 257--269. 2005.
• 5: C. Chekuri , M. T. Hajiaghayi , G. Kortsarz , M. R. Salavatipour, Approximation Algorithms for Non-Uniform Buy-at-Bulk Network Design, Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science, p.677-686, October 21-24, 2006 [doi>10.1109/FOCS.2006.15]
• 6: Chandra Chekuri , Nitish Korula , Martin Pál, Improved algorithms for orienteering and related problems, Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms, p.661-670, January 20-22, 2008, San Francisco, California
• 7: S. Dye, L. Stougie, A. Tomasgard. The stochastic single resource service-provision problem. Nav. Res. Logist., 50(8):869--887, 2003.
• 8: Friedrich Eisenbrand , Fabrizio Grandoni , Thomas Rothvoß , Guido Schäfer, Approximating connected facility location problems via random facility sampling and core detouring, Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms, p.1174-1183, January 20-22, 2008, San Francisco, California
• 9: 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]
• 10: Naveen Garg , Rohit Khandekar , Goran Konjevod , R. Ravi , F. S. Salman , Amitabh Sinha, On the Integrality Gap of a Natural Formulation of the Single-Sink Buy-at-Bulk Network Design Problem, Proceedings of the 8th International IPCO Conference on Integer Programming and Combinatorial Optimization, p.170-184, June 13-15, 2001
• 11: 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]
• 12: Sudipto Guha , Adam Meyerson , Kamesh Munagala, A constant factor approximation for the single sink edge installation problems, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.383-388, July 2001, Hersonissos, Greece [doi>10.1145/380752.380827]
• 13: Anupam Gupta , Mohammadtaghi Hajiaghayi , Amit Kumar, Stochastic Steiner Tree with Non-uniform Inflation, Proceedings of the 10th International Workshop on Approximation and the 11th International Workshop on Randomization, and Combinatorial Optimization. Algorithms and Techniques, August 20-22, 2007, Princeton, NJ, USA [doi>10.1007/978-3-540-74208-1_10]
• 14: 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]
• 15: A. Gupta, M. Pál. Stochastic Steiner trees without a root. In 32nd ICALP, LNCS, vol. 3580, 1051--1063. 2005.
• 16: 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]
• 17: A. Gupta, M. Pál, R. Ravi, A. Sinha. What about Wednesday? approximation algorithms for multistage stochastic optimization. In ph8th APPROX, LNCS, vol. 3624, 86--98. 2005.
• 18: Anupam Gupta , R. Ravi , Amitabh Sinha, LP Rounding Approximation Algorithms for Stochastic Network Design, Mathematics of Operations Research, v.32 n.2, p.345-364, May 2007 [doi>10.1287/moor.1060.0237]
• 19: Ara Hayrapetyan , Chaitanya Swamy , Éva Tardos, Network design for information networks, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
• 20: 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
• 21: 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
• 22: R. Ravi, A. Sinha. Hedging uncertainty: Approximation algorithms for stochastic optimization problems. In 10th IPCO, 101--115. 2004.
• 23: 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]
• 24: D. P. Williamson, A. van Zuylen. A simpler and better derandomization of an approximation algorithm for single-source rent-or-buy. Operations Research Letters, 35(6):707--712, 2007.

INDEX TERMS

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

General Terms:
Algorithms, Theory

Keywords:
approximation algorithms, stochastic algorithms