A subset spanner for Planar graphs,: with application to subset TSP

ABSTRACT

Let ε>0 be a constant. For any edge-weighted planar graph G and a subset S of nodes of G, there is a subgraph H of G of weight a constant times that of the minimum Steiner tree for S such that distances in H between nodes in S are at most 1+ε times the corresponding distances in G. As a consequence, there is an O(n log n)-time approximation scheme for finding a TSP among a given subset of nodes of a planar graph. This is the first PTAS for the problem.

REFERENCES

• 1: Umut A. Acar , Guy E. Blelloch , Robert Harper , Jorge L. Vittes , Shan Leung Maverick Woo, Dynamizing static algorithms, with applications to dynamic trees and history independence, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
• 2: Stephen Alstrup , Jacob Holm , Kristian De Lichtenberg , Mikkel Thorup, Maintaining information in fully dynamic trees with top trees, ACM Transactions on Algorithms (TALG), v.1 n.2, p.243-264, October 2005 [doi>10.1145/1103963.1103966]
• 3: Ingo Althöfer , Gautam Das , David Dobkin , Deborah Joseph , José Soares, On sparse spanners of weighted graphs, Discrete & Computational Geometry, v.9 n.1, p.81-100, 1993 [doi>10.1007/BF02189308]
• 4: 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 [doi>10.1145/290179.290180]
• 5: Sanjeev Arora , Michelangelo Grigni , David Karger , Philip Klein , Andrzej Woloszyn, A polynomial-time approximation scheme for weighted planar graph TSP, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.33-41, January 25-27, 1998, San Francisco, California, United States
• 6: R. F. Cohen, R. Tamassia, "Combine and Conquer," Algorithmica 18(3), pp. 324--362 (1997).
• 7: Gautam Das , Deborah Joseph, Which Triangulations Approximate the Complete Graph?, Proceedings of the International Symposium on Optimal Algorithms, p.168-192, May 29-June 02, 1989
• 8: 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
• 9: Erik D. Demaine , MohammadTaghi Hajiaghayi, Bidimensionality: new connections between FPT algorithms and PTASs, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
• 10: Greg N. Frederickson, Ambivalent Data Structures for Dynamic 2-Edge-Connectivity and k Smallest Spanning Trees, SIAM Journal on Computing, v.26 n.2, p.484-538, April 1997 [doi>10.1137/S0097539792226825]
• 11: M. Grigni , E. Koutsoupias , C. Papadimitriou, An approximation scheme for planar graph TSP, Proceedings of the 36th Annual Symposium on Foundations of Computer Science (FOCS'95), p.640, October 23-25, 1995
• 12: Michelangelo Grigni, Approximate TSP in Graphs with Forbidden Minors, Proceedings of the 27th International Colloquium on Automata, Languages and Programming, p.869-877, July 09-15, 2000
• 13: Philip Klein, Preprocessing an undirected planar network to enable fast approximate distance queries, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.820-827, January 06-08, 2002, San Francisco, California
• 14: Philip N. Klein, Multiple-source shortest paths in planar graphs, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
• 15: Philip N. Klein, A linear-time approximation scheme for planar weighted TSP, Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, p.647-657, October 23-25, 2005 [doi>10.1109/SFCS.2005.7]
• 16: Christos Levcopoulos , Andrzej Lingas, Ther Are Planar Graphs Almost as Good as the Complete Graphs and as Short as Minimum Spanning Trees, Proceedings of the International Symposium on Optimal Algorithms, p.9-13, May 29-June 02, 1989
• 17: 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]
• 18: Kurt Mehlhorn, A faster approximation algorithm for the Steiner problem in graphs, Information Processing Letters, v.27 n.3, p.125-128, March 25, 1988 [doi>10.1016/0020-0190(88)90066-X]
• 19: Christos H. Papadimitriou , Mihalis Yannakakis, The traveling salesman problem with distances one and two, Mathematics of Operations Research, v.18 n.1, p.1-11, Feb. 1993 [doi>10.1287/moor.18.1.1]
• 20: Satish B. Rao , Warren D. Smith, Approximating geometrical graphs via “spanners” and “banyans”, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.540-550, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276868]
• 21: Daniel D. Sleator , Robert Endre Tarjan, A data structure for dynamic trees, Journal of Computer and System Sciences, v.26 n.3, p.362-391, June 1983 [doi>10.1016/0022-0000(83)90006-5]
• 22: Mikkel Thorup, Compact oracles for reachability and approximate distances in planar digraphs, Journal of the ACM (JACM), v.51 n.6, p.993-1024, November 2004 [doi>10.1145/1039488.1039493]
• 23: Robert E. Tarjan , Renato F. Werneck, Self-adjusting top trees, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems

General Terms:
Algorithms

Keywords:
approximation scheme, planar graph, spanner, traveling salesman problem