APPROXIMATING TSP ON METRICS WITH BOUNDED GLOBAL GROWTH.

The traveling salesman problem (TSP) is a canonical NP-complete problem which is proved by Trevisan [SIAM J. Comput., 30 (2000), pp. 475-485] to be MAX-SNP hard even on high-dimensional Euclidean metrics. To circumvent this hardness, researchers have been developing approximation schemes for "simpler" instances of the problem. For instance, the algorithms of Arora and of Talwar show how to approximate TSP on low-dimensional metrics (for different notions of metric 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 define a global notion of dimension that generalizes the popular notion of doubling dimension, but still allows some small dense regions; e.g., it allows some metrics that contain cliques of size √n. Given a metric with global dimension dimC, we give a (1+ε)-approximation algorithm that runs in subexponential time, i.e., in exp(O(nδε-4dimC ))-time for every constant 0 < δ < 1. As mentioned above, metrics with bounded dimC may contain metrics of size O(√n) on which the TSP problem is hard to approximate to within (1 + ε). Hence, to do better than a running time of Ω(exp{√n}), our algorithms find O(1)-approximations to some portions of the tour, and (1 + ε)-approximations for other portions, and stitch them together. Moreover, we show that such globally bounded metrics have spanners that preserve distances to arbitrary accuracy and have size θ(n1.5). [ABSTRACT FROM AUTHOR]