Improved approximation guarantees for minimum-weight k-trees and prize-collecting salesmen

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Improved approximation guarantees for minimum-weight k-trees and prize-collecting salesmen

Full text

Pdf (649 KB)

Source

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

Las Vegas, Nevada, United States

Pages: 277 - 283

Year of Publication: 1995

ISBN:0-89791-718-9

Authors

Baruch Awerbuch	Johns Hopkins University, Baltimore, MD and MIT Lab. for Computer Science
Yossi Azar	Department of Computer Science, Tel Aviv University
Avrim Blum	School of Computer Science, 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): 2, Downloads (12 Months): 25, Citation Count: 15

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/225058.225139 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.

	AAG93	Baruch Awerbuch, Yossi Azar. and Rainer Gawlick. Dense trees and com-petitive selective multicast. unpub-lished manuscript, December 1993.
	Bal89	E. Balas. The prize collecting traveling salesman problem. Networks, 19:621- 636, 1989.
	BCC+94	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]
	BCV95	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]
	CK94	Shun Yan Cheung and Akhil Ku-mar. Efficient quorumcast routing al-gorithms. In Proceedings of INFO-COM '94, volume 2, pages 840-855, Toronto, Ontario, 1994.
	GH94	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]
	GLV87	B.L. Golden, L. Levy, and R. Vohra. The orienteering problem. Naval Re-search Logistics, 34:307-318, 1987.
	GW92	Michel X. Goemans , David P. Williamson, A general approximation technique for constrained forest problems, Proceedings of the third annual ACM-SIAM symposium on Discrete algorithms, p.307-316, September 1992, Orlando, Florida, United States
	RSM+94	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 15

	Fedor V. Fomin , Andrej Lilngas, Approximation algorithms for time-dependent orienteering, Information Processing Letters, v.83 n.2, p.57-62, 31 July 2002
	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
	Cristian S. Mata , Joseph S. B. Mitchell, Approximation algorithms for geometric tour and network design problems (extended abstract), Proceedings of the eleventh annual symposium on Computational geometry, p.360-369, June 05-07, 1995, Vancouver, British Columbia, Canada
	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
	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
	Baruch Awerbuch , Tripurari Singh, Online algorithms for selective multicast and maximal dense trees, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.354-362, May 04-06, 1997, El Paso, Texas, 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
	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
	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
	Esther M. Arkin , Joseph S. B. Mitchell , Giri Narasimhan, Resource-constrained geometric network optimization, Proceedings of the fourteenth annual symposium on Computational geometry, p.307-316, June 07-10, 1998, Minneapolis, Minnesota, United States
	Christian Blum , Matthias Ehrgott, Local search algorithms for the k-cardinality tree problem, Discrete Applied Mathematics, v.128 n.2-3, p.511-540, 01 June 2003
	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
	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
	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
	Gil Ben-Artzi , Hagit Hel-Or , Yacov Hel-Or, The Gray-Code Filter Kernels, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.29 n.3, p.382-393, March 2007