An Improved Approximation Ratio for the Covering Steiner Problem

by Anupam Gupta and Aravind Srinivasan

Theory of Computing, Volume 2(3), pp. 53-64, 2006

Bibliography with links to cited articles

[1]   Yair Bartal: Probabilistic approximations of metric spaces and its algorithmic applications. In Proceedings of the 37th Annual IEEE Symposium on Foundations of Computer Science, pp. 184–193, 1996. [FOCS:10.1109/SFCS.1996.548477].

[2]   Moses Charikar, Chandra Chekuri, Ashish Goel, and Sudipto Guha: Rounding via trees: deterministic approximation algorithms for group Steiner trees and k median. In Proceedings of the 30th Annual Symposium on the Theory of Computing, pp. 114–123, 1998. [STOC:10.1145/276698.276719].

[3]   Guy Even, Guy Kortsarz, and Wolfgang Slany: On network design problems: fixed cost flows and the covering Steiner problem. ACM Trans. Algorithms, 1(1):74–101, 2005. [TALG:10.1145/1077464.1077470].

[4]   Jittat Fakcharoenphol, Satish Rao, and Kunal Talwar: A tight bound on approximating arbitrary metrics by tree metrics. J. Comput. System Sci., 69(3):485–497, 2004. [JCSS:10.1016/j.jcss.2004.04.011].

[5]   Naveen Garg: Saving an epsilon: a 2-approximation for the k-mst problem in graphs. In Proceedings of the 37th Annual ACM Symposium on Theory of Computing, Baltimore, MD, USA, May 22-24, 2005, pp. 396–402, 2005. [STOC:10.1145/1060590.1060650].

[6]   Naveen Garg, Goran Konjevod, and R. Ravi: A polylogarithmic approximation algorithm for the group Steiner tree problem. Journal of Algorithms, 37(1):66–84, 2000. [JAlg:10.1006/jagm.2000.1096].

[7]   Eran Halperin, Guy Kortsarz, Robert Krauthgamer, Aravind Srinivasan, and Nan Wang: Integrality ratio for group Steiner trees and directed Steiner trees. In 14th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 275–284, January 2003. [SODA:644108.644155].

[8]   Eran Halperin and Robert Krauthgamer: Polylogarithmic inapproximability. In Proceedings of the thirty-fifth ACM symposium on Theory of computing, pp. 585–594. ACM Press, 2003. [STOC:10.1145/780542.780628].

[9]   Svante Janson: Poisson approximation for large deviations. Random Structures and Algorithms, 1(2):221–229, 1990.

[10]   Rohit Khandekar: Lagrangian Relaxation based Algorithms for Convex Programming Problems. PhD thesis, Indian Institute of Technology, New Delhi, March 2004.

[11]   Goran Konjevod, R. Ravi, and Aravind Srinivasan: Approximation algorithms for the covering Steiner problem. Random Structures and Algorithms, 20(3):465–482, 2002. Special Issue on Probabilistic methods in combinatorial optimization. [RSA:10.1002/rsa.10038].

[12]   Aravind Srinivasan: New approaches to covering and packing problems. In Proceedings of the Twelfth Annual ACM-SIAM Symposium on Discrete Algorithms (Washington, DC, 2001), pp. 567–576, Philadelphia, PA, 2001. SIAM. [SODA:365411.365535].