{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,22]],"date-time":"2026-08-22T09:13:25Z","timestamp":1787390005482,"version":"build-2736575974"},"reference-count":52,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2012,1]]},"abstract":"<jats:p>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 \u201esimpler\u201d 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 \u201elocal\u201d: 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 $\\sqrt{n}$. Given a metric with global dimension $\\dim_{C}$, we give a $(1+\\varepsilon)$-approximation algorithm that runs in subexponential time, i.e., in $\\exp(O(n^{\\delta}\\varepsilon^{-4\\dim_{C}}))$-time for every constant $0&lt;\\delta&lt;1$. As mentioned above, metrics with bounded $\\dim_{C}$ may contain metrics of size $O(\\sqrt{n})$ on which the TSP problem is hard to approximate to within $(1+\\varepsilon)$. Hence, to do better than a running time of $\\Omega(\\exp\\{\\sqrt{n}\\})$, our algorithms find $O(1)$-approximations to some portions of the tour, and $(1+\\varepsilon)$-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 $\\Theta(n^{1.5})$.<\/jats:p>","DOI":"10.1137\/090749396","type":"journal-article","created":{"date-parts":[[2012,5,31]],"date-time":"2012-05-31T19:23:02Z","timestamp":1338492182000},"page":"587-617","source":"Crossref","is-referenced-by-count":4,"title":["Approximating TSP on Metrics with Bounded Global Growth"],"prefix":"10.1137","volume":"41","author":[{"given":"T.-H.","family":"Hubert Chan","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Anupam","family":"Gupta","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2012,5,31]]},"reference":[{"key":"atypb1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02189308"},{"key":"atypb2","doi-asserted-by":"publisher","DOI":"10.1109\/ICDCS.2006.72"},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.1145\/1073970.1073978"},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(89)90031-0"},{"key":"atypb5","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1996.548458"},{"key":"atypb6","doi-asserted-by":"publisher","DOI":"10.1145\/290179.290180"},{"key":"atypb7","first-page":"207","volume-title":"The Traveling Salesman Problem and Its Variations, Comb. Optim. 12","author":"Arora S.","year":"2002"},{"key":"atypb8","first-page":"106","volume-title":"Proceedings of the 13th Annual ACM Symposium on Theory of Computing (STOC '98)","author":"Arora S.","year":"1999"},{"key":"atypb9","doi-asserted-by":"publisher","DOI":"10.24033\/bsmf.1997"},{"key":"atypb10","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1996.548477"},{"key":"atypb11","first-page":"299","volume-title":"Proceedings of the 21st International Conference on Very Large Data Bases (VLDB), Morgan Kaufmann","author":"Belussi A.","year":"1995"},{"key":"atypb12","doi-asserted-by":"publisher","DOI":"10.1145\/1143844.1143857"},{"key":"atypb13","doi-asserted-by":"publisher","DOI":"10.1142\/S0218195995000088"},{"key":"atypb14","first-page":"574","volume-title":"Proceedings of the 38th Annual ACM Symposium on the Theory of Computing (STOC), ACM","author":"Cole R.","year":"2006"},{"key":"atypb15","volume-title":"Lower Bounds for Embedding into Distributions over Excluded Minor Graph Families, preprint, arXiv:0807.4582v1","author":"Carroll D. E.","year":"2008"},{"key":"atypb16","first-page":"762","volume-title":"Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), ACM","author":"Chan H. T.-H.","year":"2005"},{"key":"atypb17","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0055093"},{"key":"atypb18","doi-asserted-by":"publisher","DOI":"10.1007\/PL00009449"},{"key":"atypb19","doi-asserted-by":"publisher","DOI":"10.7551\/mitpress\/4908.003.0005"},{"key":"atypb20","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-45465-9_83"},{"key":"atypb21","volume-title":"Graph Theory","author":"Diestel R.","year":"2000","edition":"2"},{"key":"atypb22","doi-asserted-by":"publisher","DOI":"10.1145\/182591.182593"},{"key":"atypb23","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2004.04.011"},{"key":"atypb24","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"Garey M. R.","year":"1979"},{"key":"atypb25","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2003.1238226"},{"key":"atypb26","doi-asserted-by":"publisher","DOI":"10.1016\/0167-2789(83)90298-1"},{"key":"atypb27","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-45022-X_73"},{"key":"atypb28","first-page":"627","volume-title":"Proceedings of the 37th Annual IEEE Symposium on Foundations of Computer Science (FOCS), IEEE Computer Society Press","author":"J.","year":"1996"},{"key":"atypb29","doi-asserted-by":"publisher","DOI":"10.1145\/564870.564877"},{"key":"atypb30","doi-asserted-by":"publisher","DOI":"10.1145\/1064092.1064117"},{"key":"atypb31","doi-asserted-by":"publisher","DOI":"10.1201\/9781420035315.ch8"},{"key":"atypb32","doi-asserted-by":"publisher","DOI":"10.1016\/0376-5075(77)90002-2"},{"key":"atypb33","first-page":"798","volume-title":"Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), ACM","author":"Krauthgamer R.","year":"2004"},{"key":"atypb34","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2005.09.017"},{"key":"atypb35","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2006.9"},{"key":"atypb36","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2005.7"},{"key":"atypb37","doi-asserted-by":"publisher","DOI":"10.1145\/1073814.1073826"},{"key":"atypb38","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-48481-7_33"},{"key":"atypb39","doi-asserted-by":"publisher","DOI":"10.1145\/509907.510013"},{"key":"atypb40","doi-asserted-by":"publisher","DOI":"10.1007\/11682462_59"},{"key":"atypb41","doi-asserted-by":"publisher","DOI":"10.1145\/1146381.1146412"},{"key":"atypb42","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2004.70"},{"key":"atypb43","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4613-0039-7"},{"key":"atypb44","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539796309764"},{"key":"atypb45","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2000.839457"},{"key":"atypb46","doi-asserted-by":"publisher","DOI":"10.1007\/s002240000118"},{"key":"atypb47","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.3190130114"},{"key":"atypb48","doi-asserted-by":"publisher","DOI":"10.1287\/moor.18.1.1"},{"key":"atypb49","first-page":"540","volume-title":"Proceedings of the Annual ACM Symposium on Theory of Computing, ACM","author":"Rao S. B.","year":"1999"},{"key":"atypb50","doi-asserted-by":"publisher","DOI":"10.1145\/1073814.1073823"},{"key":"atypb51","doi-asserted-by":"publisher","DOI":"10.1145\/1007352.1007399"},{"key":"atypb52","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539799352735"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/090749396","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:06:45Z","timestamp":1787339205000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/090749396"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,1]]},"references-count":52,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2012,1]]}},"alternative-id":["10.1137\/090749396"],"URL":"https:\/\/doi.org\/10.1137\/090749396","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,1]]}}}