Approximating geometrical graphs via “spanners” and “banyans”

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Approximating geometrical graphs via “spanners” and “banyans”

Full text

Pdf (1.70 MB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the thirtieth annual ACM symposium on Theory of computing table of contents

Dallas, Texas, United States

Pages: 540 - 550

Year of Publication: 1998

ISBN:0-89791-962-9

Authors

Satish B. Rao	NECI, 4 Independence way, Princeton, NJ
Warren D. Smith	NECI, 4 Independence way, Princeton, NJ

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 0, Downloads (12 Months): 22, Citation Count: 18

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/276698.276868 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	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
	2	Sunil Arya , Gautam Das , David M. Mount , Jeffrey S. Salowe , Michiel Smid, Euclidean spanners: short, thin, and lanky, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.489-498, May 29-June 01, 1995, Las Vegas, Nevada, United States [doi>10.1145/225058.225191]
	3	J.E. Beasley and F.Goffmet. A Delaunay triangulationbased heuristic for the Euclidean Steiner problem. Networks, pages 215-224, 1994.
	4	Bernard Chazelle, A Faster Deterministic Algorithm for Minimum Spanning Trees, Proceedings of the 38th Annual Symposium on Foundations of Computer Science (FOCS '97), p.22, October 19-22, 1997
	5	N. Christophides. Worst-case analysis of a new heuristic for the traveling salesman problem. In J.F.Traub, editor, Symposium on new directions and recent reaults in algorithms and complexity. Academic Press, 1976.
	6	G. Das, S. Kapoor, and M. Staid. On the complexity of approximating Euclidean traveling salesman tours and minimum spanning trees. Algorithmica, 19:447-460, 1997.
	7	Gautam Das , Giri Narasimhan , Jeffrey Salowe, A new way to weigh Malnourished Euclidean graphs, Proceedings of the sixth annual ACM-SIAM symposium on Discrete algorithms, p.215-222, January 22-24, 1995, San Francisco, California, United States
	8	D. Z. Du and F. K. Hwang. A proof of the Gilbert-Pollal: conjecture on the Steiner ratio. Algorithmica, 7:121-135, 1992.
	9	Emile Aarts , Jan K. Lenstra, Local Search in Combinatorial Optimization, John Wiley & Sons, Inc., New York, NY, 1997
	10	Ulrich Fößmeier , Michael Kaufmann, Solving Rectilinear Steiner Tree Problems Exactly in Theory and Practice, Proceedings of the 5th Annual European Symposium on Algorithms, p.171-185, September 15-17, 1997
	11	M. R. Garey, R. L. Graham, and D. S. Johnson. The complexity of computing Steiner minimal trees. SiAM J. Appl. Math., 32(4):835-859, 1977.
	12	E.N. Gilbert and H.O. Pollak. Steiner minimal trees. SIAM J. Appl. Math., 16(1):1-29, 1968.
	13	Michel X. Goemans, Worst-case comparison of valid inequalities for the TSP, Mathematical Programming: Series A and B, v.69 n.2, p.335-349, Aug. 25, 1995
	14	M. Held and R.M. Karp. The traveling salesman problem and minimum spanning trees. Operations Research, 18:1138-1162, 1970.
	15	F.K. Hwang. On Steiner minimal trees with rectilinear distance. SIAM J. Appl. Math., 30(1):104-114, 1976.
	16	R.M. Karp. Probabilistic analysis of partitioning algorithms for the TSP in the plane. Math. Oper. Rca., 2:209- 224, 1977.
	17	E.L. Lawler, j.K. Lenstra, A.H.G. Rinnooy Kan, and D.B. Shmoys, editors. The traveling salesman problem. j.Wiley, 1985.
	18	J. Van Leeuwen and A.A. Schoone. Untangling a traveling salesman tour in the plane. In Proc. 7th conf. on graphtheoretic concepts in computer sci. (WG 81)~ Linz, Austria, pages 87-98, 1981.
	19	S. Lin and B. Kernighan. An effective heuristic algorithm for the travelling-salesman problem. Operations Research, 21:498-516, 1973.
	20	Manfred Padberg , Giovanni Rinaldi, A branch-and-cut algorithm for the resolution of large-scale symmetric traveling salesman problems, SIAM Review, v.33 n.1, p.60-100, March 1991 [doi>10.1137/1033004]
	21	Christos H. Papadimitriou, The complexity of the Lin-Kernighan heuristic for the traveling salesman problem, SIAM Journal on Computing, v.21 n.3, p.450-465, June 1992 [doi>10.1137/0221030]
	22	D. B. Shmoys , D. P. Williamson, Analyzing the Held-Karp TSP bound: a monotonicity property with application, Information Processing Letters, v.35 n.6, p.281-285, Sep. 1990 [doi>10.1016/0020-0190(90)90028-V]
	23	Warren Douglas Smith, Studies in computational geometry motivated by mesh generation, 1989
	24	W.D. Smith. How to find Steiner minimal trees in dspace. Algorithmica, 7:137-177, 1992.
	25	Luca Trevisan, When Hamming meets Euclid: the approximability of geometric TSP and MST (extended abstract), Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.21-29, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258541]
	26	David M. Warme. A new exact algorithm for rectilinear steiner trees. In International Symposium on Mathematical Programming, Lausanne, Switzerland, 1997.
	27	P. Winter and M. Zachariasen. Euclidean Steiner minimal trees, an improved exact algorithm. Networka, 30(3):149-166, 1997.

CITED BY 17

	Kasturi R. Varadarajan , Pankaj K. Agarwal, Approximation algorithms for bipartite and non-bipartite matching in the plane, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.805-814, January 17-19, 1999, Baltimore, Maryland, United States
	Timothy M. Chan, Polynomial-time approximation schemes for packing and piercing fat objects, Journal of Algorithms, v.46 n.2, p.178-189, February 2003
	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
	Artur Czumaj , Andrzej Lingas, On approximability of the minimum-cost k-connected spanning subgraph problem, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.281-290, January 17-19, 1999, Baltimore, Maryland, United States
	Pankaj K. Agarwal , Micha Sharir, Efficient algorithms for geometric optimization, ACM Computing Surveys (CSUR), v.30 n.4, p.412-458, Dec. 1998
	Artur Czumaj , Hairong Zhao, Fault-tolerant geometric spanners, Proceedings of the nineteenth annual symposium on Computational geometry, June 08-10, 2003, San Diego, California, USA
	Kunal Talwar, Bypassing the embedding: algorithms for low dimensional metrics, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA
	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
	Mohammad Farshi , Panos Giannopoulos , Joachim Gudmundsson, Finding the best shortcut in a geometric network, Proceedings of the twenty-first annual symposium on Computational geometry, June 06-08, 2005, Pisa, Italy
	Philip N. Klein, A subset spanner for Planar graphs,: with application to subset TSP, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA
	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
	Glencora Borradaile , Claire Kenyon-Mathieu , Philip Klein, A polynomial-time approximation scheme for Steiner tree in planar graphs, Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, p.1285-1294, January 07-09, 2007, New Orleans, Louisiana
	Timothy M. Chan, Well-separated pair decomposition in linear time?, Information Processing Letters, v.107 n.5, p.138-141, August, 2008
	T-H. Hubert Chan , Anupam Gupta, Approximating TSP on metrics with bounded global growth, Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms, p.690-699, January 20-22, 2008, San Francisco, California
	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
	Glencora Borradaile , Philip Klein , Claire Mathieu, An O(n log n) approximation scheme for Steiner tree in planar graphs, ACM Transactions on Algorithms (TALG), v.5 n.3, p.1-31, July 2009
	Christian Schindelhauer , Klaus Volbert , Martin Ziegler, Geometric spanners with applications in wireless networks, Computational Geometry: Theory and Applications, v.36 n.3, p.197-214, April, 2007