Resource-constrained geometric network optimization

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Resource-constrained geometric network optimization

Full text

Pdf (1.46 MB)

Source

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

Minneapolis, Minnesota, United States

Pages: 307 - 316

Year of Publication: 1998

ISBN:0-89791-973-4

Authors

Esther M. Arkin	Department of Applied Mathematics and Statistics, State University of New York, Stony Brook, NY
Joseph S. B. Mitchell	Department of Applied Mathematics and Statistics, State University of New York, Stony Brook, NY
Giri Narasimhan	Department of Mathematical Sciences, University of Memphis, Memphis, TN

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): 6, Downloads (12 Months): 34, Citation Count: 6

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/276884.276919 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	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]
	2	E. M. Arkin, S. Khuller, and J. S. B. Mitchell. Geometric knapsack problems. Algorithmica, 10:399-427, 1993.
	3	E. M. Arkin, J. S. B. Mitchell, and G. D. Piatko. Bicrit,:ria shortest path problems in the plane. In Proc. 3rd Canad. Conf. Uompu#. Geom., pages 153-156, 1991.
	4	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
	5	S. Arora, Nearly linear time approximation schemes for Euclidean TSP and other geometric problems, Proceedings of the 38th Annual Symposium on Foundations of Computer Science (FOCS '97), p.554, October 19-22, 1997
	6	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]
	7	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]
	8	E. Bolas, The prize collecting traveling salesman problem. Networhst 19:621-636# 1989.
	9	J, L, Bentley. Fast algorithms for geometric traveling salesman problems, ORSA J. Comput., 4(4):387-411,1992.
	10	Daniel Bienstock , Michel X. Goemans , David Simchi-Levi , David Williamson, A note on the prize collecting traveling salesman problem, Mathematical Programming: Series A and B, v.59 n.3, p.413-420, May 7, 1993 [doi>10.1007/BF01581256]
	11	David Eppstein , Mark Overmars , Günter Rote , Gerhard Woeginger, Finding minimum area k-gons, Discrete & Computational Geometry, v.7 n.1, p.45-58, 1992 [doi>10.1007/BF02187823]
	12	M, Fi#chetti, H. W. Hamacher, K. JOrnsten, and F. Maffiolt, Weighted k-cardinality trees: Complexity and polyhedral structure, Networks, 24:11-21, 1994.
	13	M. R. Oarey# R. L, Graham, and D. S. Johnson. The complexity of computing Steiner minimal trees. SIAM J. AppL Math,, 32:835-859, 1977.
	14	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
	15	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
	16	B, L, Goldent L. Levy, and R. Vohra. The orienteering problem. Naval Res. Logistlcs# 34:307-318,1991.
	17	M, Jiingert G, Reinelt, and G. Rinaldi. The traveling salesman problem. In M. O. Ball, T. L. Magnanti, O. L. Monma, and G. L, Nemhauser, editors, Network Models, Handbook of Operations Research/Management Science, pages 225-330. Elsevier Science, Amsterdam, 1995.
	18	E, L, Lawler, J. K, Lenstra, A. H. G. Rinnooy Kan, and D. B, Shmoys# editors. The Traveling Salesman Problem. Wlley# New York, NY# 1985.
	19	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 [doi>10.1145/220279.220318]
	20	Joseph S. B. Mitchell, Shortest paths and networks, Handbook of discrete and computational geometry, CRC Press, Inc., Boca Raton, FL, 1997
	21	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
	22	J. S, B, Mitdmll, Geometric shortest paths and network optimization. In J.-R. Sack and J. Urrutia, editors, Handbook of Computational Geometry. Elsevier Science, Amsterdam, 1998f to appear.
	23	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]
	24	J. S, B, Mitchell. Guillotine subdivisions approximate polygonal subdlvislons: ParL iII- Faster polynomial-time approximation schemes for geometric network optimization. Manuncr\|pt, 1997.
	25	J, S, B, Mitchell, O. Piatko, and E. M. Arkin. Computing a dmrtcnt k-link path in a polygon. In Pros. 33rd Annu. IEEE ,qympoz. Found, Oomput. Sci., pages 573-582, 1992.
	26	T. Nishizeki and N. Chiba. Planar graphs: Theory and algorithms, Ann, Discrete Math., 32, 1988.
	27	S. B. Rao and W. D. Smith. Improved approximation schemes for travelingsalesman tours. Pros. 30th Annu. A CM Sympos. Theory Comput., to appear, 1998.
	28	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
	29	G. Reinelt. Fast heuristics for large geometric traveling salesman problems. ORSA J. Comput., 4:206-217', 1992.
	30	T. Tsiligirides. Heuristic methods applied to orienteerlng. J.
	31	A. Zelikovsky and D. Lozevanu. Minimal and bounded trees. In Tezeie Gong. XVII{Aead. Romano-Americane, Kishinev, pages 25-26, 1993.

CITED BY 6

	Fedor V. Fomin , Andrej Lilngas, Approximation algorithms for time-dependent orienteering, Information Processing Letters, v.83 n.2, p.57-62, 31 July 2002
	Nikhil Bansal , Avrim Blum , Shuchi Chawla , Adam Meyerson, Approximation algorithms for deadline-TSP and vehicle routing with time-windows, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA
	Ke Chen , Sariel Har-Peled, The orienteering problem in the plane revisited, Proceedings of the twenty-second annual symposium on Computational geometry, June 05-07, 2006, Sedona, Arizona, USA
	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
	Pieter Vansteenwegen , Wouter Souffriau , Greet Vanden Berghe , Dirk Van Oudheusden, Iterated local search for the team orienteering problem with time windows, Computers and Operations Research, v.36 n.12, p.3281-3290, December, 2009
	Amarjeet Singh , Andreas Krause , Carlos Guestrin , William J. Kaiser, Efficient informative sensing using multiple robots, Journal of Artificial Intelligence Research, v.34 n.1, p.707-755, January 2009