Approximation algorithms for geometric tour and network design problems (extended abstract)

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Approximation algorithms for geometric tour and network design problems (extended abstract)

Full text

Pdf (1.16 MB)

Source

Annual Symposium on Computational Geometry archive
Proceedings of the eleventh annual symposium on Computational geometry table of contents

Vancouver, British Columbia, Canada

Pages: 360 - 369

Year of Publication: 1995

ISBN:0-89791-724-3

Authors

Cristian S. Mata	Department of Computer Science, SUNY Stony Brook, NY
Joseph S. B. Mitchell	Department of Applied Mathematics and Statistics, State University of New York, Stony Brook, NY

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
SIGGRAPH: ACM Special Interest Group on Computer Graphics and Interactive Techniques

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 8, Downloads (12 Months): 49, Citation Count: 20

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/220279.220318 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	Pankaj K. Agarwal , Subhash Suri, Surface approximation and geometric partitions, Proceedings of the fifth annual ACM-SIAM symposium on Discrete algorithms, p.24-33, January 23-25, 1994, Arlington, Virginia, United States
	2	Esther M. Arkin , Refael Hassin, Approximation algorithms for the geometric covering salesman problem, Discrete Applied Mathematics, v.55 n.3, p.197-218, Dec. 13, 1994 [doi>10.1016/0166-218X(94)90008-6]
	3	E. M. Arkin, S. Khuller, and J. S. B. Mitchell. Geometric knapsack problems. AIgorithmica, 10:399-427, 1993.
	4	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]
	5	M. de Berg and M. van Kreveld. Rectilinear decompositions with low stabbing number. Tech. Report RUU-CS-93-25, Dept. Comput. Sci., Utrecht Univ., 1993.
	6	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]
	7	Svante Carlsson , Håkan Jonsson , Bengt J. Nilsson, Finding the Shortest Watchman Route in a Simple Polygon, Proceedings of the 4th International Symposium on Algorithms and Computation, p.58-67, December 15-17, 1993
	8	Wei-pang Chin, Optimum watchman routes, Information Processing Letters, v.28 n.1, p.39-44, May 30, 1988 [doi>10.1016/0020-0190(88)90141-X]
	9	N. Christofides., Worst-case analysis of a new heuristic for the traveling salesman problem. In J. F. Traub, editor, $ympos. on New Directions and Recent Results in Algorithms and Complexity, New York, NY, 1976. Academic Press.
	10	Kenneth L. Clarkson, Approximation algorithms for planar traveling salesman tours and minimum-length triangulations, Proceedings of the second annual ACM-SIAM symposium on Discrete algorithms, p.17-23, January 28-30, 1991, San Francisco, California, United States
	11	D.-Z. Du, L.-Q. Pan, and M.-T. Shing. Minimum edge length guillotine rectangular partition. Report 02418-86, Math. Sci. Res. Inst., Univ. California, Berkeley, CA, 1986.
	12	Peter Eades , David Rappaport, The complexity of computing minimum separating polygons, Pattern Recognition Letters, v.14 n.9, p.715-718, Sept. 1993 [doi>10.1016/0167-8655(93)90140-9]
	13	David Eppstein, Approximating the minimum weight triangulation, Proceedings of the third annual ACM-SIAM symposium on Discrete algorithms, p.48-57, September 1992, Orlando, Florida, United States
	14	S. Fekete. On the complexity of rain-link red-blue separation. Manuscript, 1992.
	15	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]
	16	T. Gonzalez, M. Razzazi, and S.-Q. Zheng. An efficient divideand-conquer approximation algorithm for hyperrectangular partitions. In Proc. 2nd Canad. Con}. Comput. Geom., pages 214-217, 1990.
	17	John Hershberger , Subhash Suri, A pedestrian approach to ray shooting: shoot a ray, take a walk, Proceedings of the fourth annual ACM-SIAM Symposium on Discrete algorithms, p.54-63, January 25-27, 1993, Austin, Texas, United States
	18	Edmund Ihler , Gabriele Reich , Peter Widmayer, On Shortest Networks for Classes of Points in the Plane, Proceedings of the International Workshop on Computational Geometry - Methods, Algorithms and Applications, p.103-111, March 21-22, 1991
	19	C Levcopoulos, Fast heuristics for minimum length rectangular partitions of polygons, Proceedings of the second annual symposium on Computational geometry, p.100-108, June 02-04, 1986, Yorktown Heights, New York, United States [doi>10.1145/10515.10526]
	20	C.I. Levcopoulos, Heuristics for minimum decompositions of polygons, Linkoping University, Linkoping, Sweden, 1987
	21	Christos Levcopoulos , Andrzej Lingas, Bounds on the Length of Convex Partitions of Polygons, Proceedings of the Fourth Conference on Foundations of Software Technology and Theoretical Computer Science, p.279-295, December 13-15, 1984
	22	J.S.B. Mitchell. Approximation algorithms for geometric separation problems. Technical report, AMS Dept., SUNY Stony Brook, NY, July 1993.
	23	B.J. Nilsson. Guarding art galleries- Methods for mobile guards. Ph.D. thesis, Lund University, 1995.
	24	Michael S. Paterson , F. Frances Yao, Efficient binary space partitions for hidden-surface removal and solid modeling, Discrete & Computational Geometry, v.5 n.5, p.485-503, 1990 [doi>10.1007/BF02187806]
	25	Michael S. Paterson , F. Frances Yao, Optimal binary space partitions for orthogonal objects, Journal of Algorithms, v.13 n.1, p.99-113, March 1992 [doi>10.1016/0196-6774(92)90007-Y]
	26	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 20

	Pankaj K. Agarwal , Leonidas J. Guibas , T. M. Murali , Jeffrey Scott Vitter, Cylindrical static and kinetic binary space partitions, Proceedings of the thirteenth annual symposium on Computational geometry, p.39-48, June 04-06, 1997, Nice, France
	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
	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
	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
	Adrian Dumitrescu , Joseph S. B. Mitchell, Approximation algorithms for TSP with neighborhoods in the plane, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.38-46, January 07-09, 2001, Washington, D.C., 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
	Xuehou Tan, Approximation algorithms for the watchman route and zookeeper's problems, Discrete Applied Mathematics, v.136 n.2-3, p.363-376, 15 February 2004
	Joachim Gudmundsson , Christos Levcopoulos, A fast approximation algorithm for TSP with neighborhoods, Nordic Journal of Computing, v.6 n.4, p.469-488, Winter 1999
	Adrian Dumitrescu , Joseph S. B. Mitchell, Approximation algorithms for TSP with neighborhoods in the plane, Journal of Algorithms, v.48 n.1, p.135-159, August 2003
	Esther M. Arkin , Joseph S. B. Mitchell , Christine D. Piatko, Minimum-link watchman tours, Information Processing Letters, v.86 n.4, p.203-207, 31 May 2003
	Hee-Kap Ahn , Otfried Cheong , Chan-Su Shin, Building bridges between convex regions, Computational Geometry: Theory and Applications, v.25 n.1-2, p.161-170, May 2003
	Mark de Berg , Joachim Gudmundsson , Matthew J. Katz , Christos Levcopoulos , Mark H. Overmars , A. Frank van der Stappen, TSP with neighborhoods of varying size, Journal of Algorithms, v.57 n.1, p.22-36, September 2005
	Shmuel Safra , Oded Schwartz, On the complexity of approximating tsp with neighborhoods and related problems, Computational Complexity, v.14 n.4, p.281-307, March 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
	Hans L. Bodlaender , Corinne Feremans , Alexander Grigoriev , Eelko Penninkx , René Sitters , Thomas Wolle, On the minimum corridor connection problem and other generalized geometric problems, Computational Geometry: Theory and Applications, v.42 n.9, p.939-951, November, 2009
	Bing Lu , Hongwei Du , Xiaohua Jia , Yinfeng Xu , Binhai Zhu, On a Minimum Linear Classification Problem, Journal of Global Optimization, v.35 n.1, p.103-109, May 2006
	Bengt J. Nilsson, Approximating a Shortest Watchman Route, Fundamenta Informaticae, v.45 n.3, p.235-281, August 2001
	Bing Lu , Yinfeng Xu , Binhai Zhu , Ding-Zhu Du, On a Minimum Linear Classification Problem, Journal of Global Optimization, v.26 n.4, p.435-441, August 2003
	Joseph S. B. Mitchell, A PTAS for TSP with neighborhoods among fat regions in the plane, Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, p.11-18, January 07-09, 2007, New Orleans, Louisiana
	Csaba D. Tóth, Binary plane partitions for disjoint line segments, Proceedings of the 25th annual symposium on Computational geometry, June 08-10, 2009, Aarhus, Denmark