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]. |
This file has been generated by bibtex2html 1.74