A 2 + &egr; approximation algorithm for the k-MST problem

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

A 2 + &egr; approximation algorithm for the k-MST problem

Full text

Pdf (597 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: 754 - 759

Year of Publication: 2000

ISBN:0-89871-453-2

Authors

Sanjeev Arora	Princeton University
George Karakostas	Princeton University

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): 27, Citation Count: 11

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	Sanjeev Arora, Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems, Journal of the ACM (JACM), v.45 n.5, p.753-782, Sept. 1998 [doi>10.1145/290179.290180]
	2	Baruch Awerbuch , Yossi Azar , Avrim Blum , Santosh Vempala, Improved approximation guarantees for minimum-weight k-trees and prize-collecting salesmen, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.277-283, May 29-June 01, 1995, Las Vegas, Nevada, United States [doi>10.1145/225058.225139]
	3	Avrim Blum , Prasad Chalasani , Don Coppersmith , Bill Pulleyblank , Prabhakar Raghavan , Madhu Sudan, The minimum latency problem, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.163-171, May 23-25, 1994, Montreal, Quebec, Canada [doi>10.1145/195058.195125]
	4	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]
	5	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
	6	Michel Goemans , Jon Kleinberg, An improved approximation ratio for the minimum latency problem, Proceedings of the seventh annual ACM-SIAM symposium on Discrete algorithms, p.152-158, January 28-30, 1996, Atlanta, Georgia, United States
	7	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]
	8	Joseph S. B. Mitchell, Guillotine Subdivisions Approximate Polygonal Subdivisions: A Simple Polynomial-Time Approximation Scheme for Geometric TSP, k-MST, and Related Problems, SIAM Journal on Computing, v.28 n.4, p.1298-1309, Aug. 1999 [doi>10.1137/S0097539796309764]
	9	S. Rajagopalan and V.V. Vazirani. Logarithmic approximation of minimum weight k-trees. Unpublished manuscript, 1995.
	10	R. Ravi , R. Sundaram , M. V. Marathe , D. J. Rosenkrantz , S. S. Ravi, Spanning trees short or small, Proceedings of the fifth annual ACM-SIAM symposium on Discrete algorithms, p.546-555, January 23-25, 1994, Arlington, Virginia, United States

CITED BY 11

	Aaron Archer , David P. Williamson, Faster approximation algorithms for the minimum latency problem, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
	Anna Moss , Yuval Rabani, Approximation algorithms for constrained for constrained node weighted steiner tree problems, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.373-382, July 2001, Hersonissos, Greece
	Goran Konjevod , R. Ravi, An approximation algorithm for the covering Steiner problem, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.338-344, January 09-11, 2000, San Francisco, California, United States
	Jittat Fakcharoenphol , Chris Harrelson , Satish Rao, The k-traveling repairman problem, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
	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
	Markus Bläser, Computing small partial coverings, Information Processing Letters, v.85 n.6, p.327-331, 31 March 2003
	Naveen Garg, Saving an epsilon: a 2-approximation for the k-MST problem in graphs, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA
	Refael Hassin , Danny Segev, Robust subgraphs for trees and paths, ACM Transactions on Algorithms (TALG), v.2 n.2, p.263-281, April 2006
	Maurizio Bruglieri , Matthias Ehrgott , Horst W. Hamacher , Francesco Maffioli, An annotated bibliography of combinatorial optimization problems with fixed cardinality constraints, Discrete Applied Mathematics, v.154 n.9, p.1344-1357, 1 June 2006
	Jittat Fakcharoenphol , Chris Harrelson , Satish Rao, The k-traveling repairmen problem, ACM Transactions on Algorithms (TALG), v.3 n.4, p.40-es, November 2007
	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