Approximating TSP on metrics with bounded global growth

ABSTRACT

The Traveling Salesman Problem (TSP) is a canonical NP-complete problem which is known to be MAX-SNP hard even on (high-dimensional) Euclidean metrics [39]. In order to circumvent this hardness, researchers have been developing approximation schemes for low-dimensional metrics [4, 38] (under different notions of dimension). However, a feature of most current notions of metric dimension is that they are "local": the definitions require every local neighborhood to be well-behaved. In this paper, we consider the case when the metric is less restricted: it has a few "dense" regions, but is "well-behaved on the average"?

To this end, we define a global notion of dimension which we call the correlation dimension (denoted by dim_C), which generalizes the popular notion of doubling dimension. In fact, the class of metrics with dim_C = O(1) not only contains all doubling metrics, but also contains some metrics containing uniform submetrics of size √n. We first show, using a somewhat "local" argument, that one can solve TSP on these metrics in time 2^O(√n); we then take advantage of the global nature of TSP (and the global nature of our definition) to give a (1 + ε)-approximation algorithm that runs in sub-exponential time: i.e., in 2^{O(nδε-4dimC)}-time for every constant 0 < δ < 1.

REFERENCES

• 1: Ittai Abraham , Cyril Gavoille , Andrew V. Goldberg , Dahlia Malkhi, Routing in Networks with Low Doubling Dimension, Proceedings of the 26th IEEE International Conference on Distributed Computing Systems, p.75, July 04-07, 2006 [doi>10.1109/ICDCS.2006.72]
• 2: Ittai Abraham , Dahlia Malkhi, Name independent routing for growth bounded networks, Proceedings of the seventeenth annual ACM symposium on Parallelism in algorithms and architectures, July 18-20, 2005, Las Vegas, Nevada, USA [doi>10.1145/1073970.1073978]
• 3: Stefan Arnborg , Andrzej Proskurowski, Linear time algorithms for NP-hard problems restricted to partial k-trees, Discrete Applied Mathematics, v.23 n.1, p.11-24, April 1989 [doi>10.1016/0166-218X(89)90031-0]
• 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 , Prabhakar Raghavan , Satish Rao, Approximation schemes for Euclidean k-medians and related problems, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.106-113, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276718]
• 6: Y. Bartal, Probabilistic approximation of metric spaces and its algorithmic applications, Proceedings of the 37th Annual Symposium on Foundations of Computer Science, p.184, October 14-16, 1996
• 7: Alberto Belussi , Christos Faloutsos, Estimating the Selectivity of Spatial Queries Using the `Correlation' Fractal Dimension, Proceedings of the 21th International Conference on Very Large Data Bases, p.299-310, September 11-15, 1995
• 8: Alina Beygelzimer , Sham Kakade , John Langford, Cover trees for nearest neighbor, Proceedings of the 23rd international conference on Machine learning, p.97-104, June 25-29, 2006, Pittsburgh, Pennsylvania [doi>10.1145/1143844.1143857]
• 9: Hubert T-H. Chan , Anupam Gupta , Bruce M. Maggs , Shuheng Zhou, On hierarchical routing in doubling metrics, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
• 10: Kenneth L. Clarkson. Nearest-neighbor searching and metric space dimensions. In G. Shakhnarovich, T. Darrell, and P. Indyk, editors, Nearest-Neighbor Methods for Learning and Vision: Theory and Practice, pages 15--59. MIT Press, 2006.
• 11: Richard Cole , Lee-Ad Gottlieb, Searching dynamic point sets in spaces with bounded doubling dimension, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA [doi>10.1145/1132516.1132599]
• 12: Artur Czumaj , Andrzej Lingas, Fast Approximation Schemes for Euclidean Multi-connectivity Problems, Proceedings of the 27th International Colloquium on Automata, Languages and Programming, p.856-868, July 09-15, 2000
• 13: Artur Czumaj , Andrzej Lingas , Hairong Zhao, Polynomial-Time Approximation Schemes for the Euclidean Survivable Network Design Problem, Proceedings of the 29th International Colloquium on Automata, Languages and Programming, p.973-984, July 08-13, 2002
• 14: Jittat Fakcharoenphol , Satish Rao , Kunal Talwar, A tight bound on approximating arbitrary metrics by tree metrics, Journal of Computer and System Sciences, v.69 n.3, p.485-497, November 2004 [doi>10.1016/j.jcss.2004.04.011]
• 15: Christos Faloutsos , Ibrahim Kamel, Beyond uniformity and independence: analysis of R-trees using the concept of fractal dimension, Proceedings of the thirteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.4-13, May 24-27, 1994, Minneapolis, Minnesota, United States [doi>10.1145/182591.182593]
• 16: Peter Grassberger and Itamar Procaccia. Measuring the strangeness of strange attractors. Physica D, 9:189--208, 1983.
• 17: 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
• 18: Anupam Gupta , Robert Krauthgamer , James R. Lee, Bounded Geometries, Fractals, and Low-Distortion Embeddings, Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, p.534, October 11-14, 2003
• 19: Sariel Har-Peled , Manor Mendel, Fast construction of nets in low dimensional metrics, and their applications, Proceedings of the twenty-first annual symposium on Computational geometry, June 06-08, 2005, Pisa, Italy [doi>10.1145/1064092.1064117]
• 20: J. Hastad, Clique is hard to approximate within n1-, Proceedings of the 37th Annual Symposium on Foundations of Computer Science, p.627, October 14-16, 1996
• 21: Kirsten Hildrum , John D. Kubiatowicz , Satish Rao , Ben Y. Zhao, Distributed object location in a dynamic network, Proceedings of the fourteenth annual ACM symposium on Parallel algorithms and architectures, August 10-13, 2002, Winnipeg, Manitoba, Canada [doi>10.1145/564870.564877]
• 22: David R. Karger , Matthias Ruhl, Finding nearest neighbors in growth-restricted metrics, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.510013]
• 23: 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]
• 24: Jon Kleinberg , Aleksandrs Slivkins , Tom Wexler, Triangulation and Embedding Using Small Sets of Beacons, Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science, p.444-453, October 17-19, 2004 [doi>10.1109/FOCS.2004.70]
• 25: Leonard Kleinrock and Farouk Kamoun. Hierarchical routing for large networks. Performance evaluation and optimization. Comput. Networks, 1(3):155--174, 1976/77.
• 26: Stavros G. Kolliopoulos , Satish Rao, A Nearly Linear-Time Approximation Scheme for the Euclidean kappa-median Problem, Proceedings of the 7th Annual European Symposium on Algorithms, p.378-389, July 16-18, 1999
• 27: Goran Konjevod, Andréa W. Richa, and Donglin Xia. On sampling in higher-dimensional peer-to-peer systems. In LATIN 2006: Theoretical informatics, volume 3887 of Lecture Notes in Comput. Sci., pages 641--652, Berlin, 2006. Springer.
• 28: Goran Konjevod , Andréa W. Richa , Donglin Xia, Optimal-stretch name-independent compact routing in doubling metrics, Proceedings of the twenty-fifth annual ACM symposium on Principles of distributed computing, July 23-26, 2006, Denver, Colorado, USA [doi>10.1145/1146381.1146412]
• 29: Robert Krauthgamer , James R. Lee, Navigating nets: simple algorithms for proximity search, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
• 30: Robert Krauthgamer , James R. Lee, The black-box complexity of nearest-neighbor search, Theoretical Computer Science, v.348 n.2, p.262-276, 8 December 2005 [doi>10.1016/j.tcs.2005.09.017]
• 31: Fabian Kuhn , Thomas Moscibroda , Roger Wattenhofer, On the locality of bounded growth, Proceedings of the twenty-fourth annual ACM symposium on Principles of distributed computing, July 17-20, 2005, Las Vegas, NV, USA [doi>10.1145/1073814.1073826]
• 32: 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]
• 33: Deflating the Dimensionality Curse Using Multiple Fractal Dimensions, Proceedings of the 16th International Conference on Data Engineering, p.589, February 28-March 03, 2000
• 34: 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]
• 35: C. G. Plaxton, R. Rajaraman, and A. W. Richa. Accessing nearby copies of replicated objects in a distributed environment. Theory Comput. Syst., 32(3):241--280, 1999. ACM Symposium on Parallel Algorithms and Architectures (Padua, 1996).
• 36: 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]
• 37: Aleksandrs Slivkins, Distance estimation and object location via rings of neighbors, Proceedings of the twenty-fourth annual ACM symposium on Principles of distributed computing, July 17-20, 2005, Las Vegas, NV, USA [doi>10.1145/1073814.1073823]
• 38: 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 [doi>10.1145/1007352.1007399]
• 39: Luca Trevisan, When Hamming Meets Euclid: The Approximability of Geometric TSP and Steiner Tree, SIAM Journal on Computing, v.30 n.2, p.475-485, 2000 [doi>10.1137/S0097539799352735]

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.2 Approximation

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

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.1 Combinatorics
          Subjects: Combinatorial algorithms
      G.2.2 Graph Theory
          Subjects: Path and circuit problems
      G.2.3 Applications

General Terms:
Algorithms, Design, Theory