TY - GEN
T1 - Approximating TSP on metrics with bounded global growth
AU - Hubert Chan, T. H.
AU - Gupta, Anupam
PY - 2008
Y1 - 2008
N2 - 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 wellbehaved. In this paper, we consider the ease 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 2O(n δε -4dimC)-time for every constant 0 < δ < 1.
AB - 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 wellbehaved. In this paper, we consider the ease 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 2O(n δε -4dimC)-time for every constant 0 < δ < 1.
UR - http://www.scopus.com/inward/record.url?scp=58449086439&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=58449086439&partnerID=8YFLogxK
M3 - Conference contribution
AN - SCOPUS:58449086439
SN - 9780898716474
T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms
SP - 690
EP - 699
BT - Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms
T2 - 19th Annual ACM-SIAM Symposium on Discrete Algorithms
Y2 - 20 January 2008 through 22 January 2008
ER -