A constant-factor approximation algorithm for the k MST problem (extended abstract)

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

A constant-factor approximation algorithm for the k MST problem (extended abstract)

Full text

Pdf (689 KB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the twenty-eighth annual ACM symposium on Theory of computing table of contents

Philadelphia, Pennsylvania, United States

Pages: 442 - 448

Year of Publication: 1996

ISBN:0-89791-785-5

Authors

Avrim Blum	School of Computer Science, Carnegie Mellon University, Pittsburgh, PA
R. Ravi	Graduate School of Industrial Administration, Carnegie Mellon University, Pittsburgh PA
Santosh Vempala	School of Computer Science, Carnegie Mellon University, Pittsburgh, PA

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 3, Downloads (12 Months): 21, Citation Count: 12

Additional Information:

references cited by index terms collaborative colleagues

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

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/237814.237992 What is a DOI?

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	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]
	2	E. Balas. The prize collecting traveling salesman problem. Networks, 19:621-636, 1989.
	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 , Prasad Chalasani , Santosh Vempala, A constant-factor approximation for the k-MST problem in the plane, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.294-302, May 29-June 01, 1995, Las Vegas, Nevada, United States [doi>10.1145/225058.225143]
	5	Naveen Garg , Dorit S. Hochbaum, An O(log k) approximation algorithm for the k minimum spanning tree problem in the plane, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.432-438, May 23-25, 1994, Montreal, Quebec, Canada [doi>10.1145/195058.195218]
	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	B.L. Golden, L. Levy, and R. Vohra. The orienteering problem. Naval Research Logistics, 34:307-318, 1987.
	9	Joseph S. B. Mitchell, Guillotine subdivisions approximate polygonal subdivisions: a simple new method for the geometric k-MST problem, Proceedings of the seventh annual ACM-SIAM symposium on Discrete algorithms, p.402-408, January 28-30, 1996, Atlanta, Georgia, United States
	10	S. Rajagopalan and V. Vazirani. Logarithmic approximation of minimum weight k trees. Unpublished manuscript, August 1995.
	11	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
	12	A. Zelikovsky and D. Lozevanu. Minimal and bounded trees, in Tezele Cong. XVIII Acad. Romano- Americane, Kishinev, pages 25-26, 1993.

CITED BY 11

	Ashish Goel , Monika R. Henzinger , Serge Plotkin, Online througput-competitive algorithm for multicast routing and admission control, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.97-106, January 25-27, 1998, San Francisco, California, United States
	Moses Charikar , Chandra Chekuri , To-yat Cheung , Zuo Dai , Ashish Goel , Sudipto Guha , Ming Li, Approximation algorithms for directed Steiner problems, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.192-200, January 25-27, 1998, San Francisco, California, United States
	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
	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
	Sudipto Guha , Anna Moss , Joseph (Seffi) Naor , Baruch Schieber, Efficient recovery from power outage (extended abstract), Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.574-582, May 01-04, 1999, Atlanta, Georgia, United States
	Madhav V. Marathe , R. Ravi , Ravi Sundaram, Service-constrained network design problems, Nordic Journal of Computing, v.3 n.4, p.367-387, Winter 1996
	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
	G. Ausiello , M. Demange , L. Laura , V. Paschos, Algorithms for the on-line quota traveling salesman problem, Information Processing Letters, v.92 n.2, p.89-94, 31 October 2004
	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
	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
	Giorgio Ausiello , Vincenzo Bonifaci , Luigi Laura, The online Prize-Collecting Traveling Salesman Problem, Information Processing Letters, v.107 n.6, p.199-204, August, 2008