An approximation algorithm for the covering Steiner problem

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

An approximation algorithm for the covering Steiner problem

Full text

Pdf (661 KB)

Source

Symposium on Discrete Algorithms archive
Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms table of contents

San Francisco, California, United States

Pages: 338 - 344

Year of Publication: 2000

ISBN:0-89871-453-2

Authors

Goran Konjevod	Dept. of Math. Sciences, Carnegie Mellon University, Pittsburgh, PA
R. Ravi	GSIA, Carnegie Mellon University, Pittsburgh, PA

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
SIAM : Society for Industrial and Applied Mathematics

Publisher

Society for Industrial and Applied Mathematics Philadelphia, PA, USA

Bibliometrics

Downloads (6 Weeks): 4, Downloads (12 Months): 24, Citation Count: 7

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	S. Arora, Polynomial time approximation schemes for Euclidean TSP and other geometric problems, Proceedings of the 37th Annual Symposium on Foundations of Computer Science, p.2, October 14-16, 1996
	2	Sanjeev Arora , George Karakostas, A 2 + &egr; approximation algorithm for the k-MST problem, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.754-759, January 09-11, 2000, San Francisco, California, United States
	3	Sunil Arya , H. Ramesh, A 2.5-factor approximation algorithm for the k-MST problem, Information Processing Letters, v.65 n.3, p.117-118, Feb. 1998 [doi>10.1016/S0020-0190(98)00010-6]
	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	Avrim Blum , R. Ravi , Santosh Vempala, A constant-factor approximation algorithm for the k MST problem (extended abstract), Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.442-448, May 22-24, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237814.237992]
	7	Moses Charikar , Chandra Chekuri , Ashish Goel , Sudipto Guha, Rounding via trees: deterministic approximation algorithms for group Steiner trees and k-median, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.114-123, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276719]
	8	L. P. Chew, There are planar graphs almost as good as the complete graph, Journal of Computer and System Sciences, v.39 n.2, p.205-219, Oct. 1989 [doi>10.1016/0022-0000(89)90044-5]
	9	M. Fischetti, H. W. Hamacher, K. Jornsten, and F. Maffioli. Weighted k-cardinality trees: complexity and polyhedral structure. Networks, 24:11-21, 1994.
	10	N. Garg, A 3-approximation for the minimum tree spanning k vertices, Proceedings of the 37th Annual Symposium on Foundations of Computer Science, p.302, October 14-16, 1996
	11	N. Garg. Personal communication, September 1999.
	12	Naveen Garg , Goran Konjevod , R. Ravi, A polylogarithmic approximation algorithm for the Steiner group tree problem, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.253-259, January 25-27, 1998, San Francisco, California, United States
	13	S. Janson. Poisson approximations for large deviations. Randoms Structures and Applications, 1:221- 230, 1990.
	14	Philip Klein , R. Ravi, A nearly best-possible approximation algorithm for node-weighted Steiner trees, Journal of Algorithms, v.19 n.1, p.104-115, July 1995 [doi>10.1006/jagm.1995.1029]
	15	G. Konjevod, R. Ravi, and F. S. Salman. On approximating planar metrics by tree metrics, manuscript, Jul. 1997.
	16	R. Ravi , R. Sundaram , M. V. Marathe , D. J. Rosenkrantz , S. S. Ravi, Spanning Trees---Short or Small, SIAM Journal on Discrete Mathematics, v.9 n.2, p.178-200, May 1996 [doi>10.1137/S0895480194266331]
	17	G. Reich , P. Widmayer, Beyond Steiner's problem: a VLSI oriented generalization, Proceedings of the fifteenth international workshop on Graph-theoretic concepts in computer science, p.196-210, March 1990, Castle Rolduc, The Netherlands

CITED BY 7

	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
	Guy Even , Guy Kortsarz, An approximation algorithm for the group Steiner problem, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.49-58, January 06-08, 2002, San Francisco, California
	Goran Konjevod , R. Ravi , Aravind Srinivasan, Approximation algorithms for the covering Steiner problem, Random Structures & Algorithms, v.20 n.3, p.465-482, May 2002
	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
	Guy Even , Guy Kortsarz , Wolfgang Slany, On network design problems: fixed cost flows and the covering steiner problem, ACM Transactions on Algorithms (TALG), v.1 n.1, p.74-101, July 2005
	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
	Chandra Chekuri , Guy Even , Guy Kortsarz, A greedy approximation algorithm for the group Steiner problem, Discrete Applied Mathematics, v.154 n.1, p.15-34, 1 January 2006