{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,13]],"date-time":"2026-01-13T01:37:50Z","timestamp":1768268270031,"version":"3.49.0"},"reference-count":32,"publisher":"Springer Science and Business Media LLC","issue":"4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Discrete Comput Geom"],"published-print":{"date-parts":[[2011,12]]},"DOI":"10.1007\/s00454-011-9337-9","type":"journal-article","created":{"date-parts":[[2011,3,17]],"date-time":"2011-03-17T15:00:54Z","timestamp":1300374054000},"page":"704-723","source":"Crossref","is-referenced-by-count":21,"title":["A QPTAS for TSP with Fat Weakly Disjoint Neighborhoods in Doubling Metrics"],"prefix":"10.1007","volume":"46","author":[{"given":"T.-H. Hubert","family":"Chan","sequence":"first","affiliation":[]},{"given":"Khaled","family":"Elbassioni","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2011,3,18]]},"reference":[{"issue":"3","key":"9337_CR1","doi-asserted-by":"crossref","first-page":"197","DOI":"10.1016\/0166-218X(94)90008-6","volume":"55","author":"E.M. Arkin","year":"1994","unstructured":"Arkin, E.M., Hassin,\u00a0R.: Approximation algorithms for the geometric covering salesman problem. Discrete Appl. Math. 55(3), 197\u2013218 (1994)","journal-title":"Discrete Appl. Math."},{"issue":"1","key":"9337_CR2","doi-asserted-by":"crossref","first-page":"11","DOI":"10.1016\/0166-218X(89)90031-0","volume":"23","author":"S. Arnborg","year":"1989","unstructured":"Arnborg,\u00a0S., Proskurowski,\u00a0A.: Linear time algorithms for NP-hard problems restricted to partial k-trees. Discrete Appl. Math. 23(1), 11\u201324 (1989)","journal-title":"Discrete Appl. Math."},{"key":"9337_CR3","series-title":"Comb. Optim.","first-page":"207","volume-title":"The Traveling Salesman Problem and Its Variations","author":"S. Arora","year":"2002","unstructured":"Arora,\u00a0S.: Approximation algorithms for geometric TSP. In: The Traveling Salesman Problem and Its Variations. Comb. Optim., vol.\u00a012, pp.\u00a0207\u2013221. Kluwer Acad., Dordrecht (2002)"},{"issue":"4","key":"9337_CR4","doi-asserted-by":"crossref","first-page":"429","DOI":"10.24033\/bsmf.1997","volume":"111","author":"P. Assouad","year":"1983","unstructured":"Assouad,\u00a0P.: Plongements Lipschitziens dans R n . Bull. Soc. Math. Fr. 111(4), 429\u2013448 (1983)","journal-title":"Bull. Soc. Math. Fr."},{"key":"9337_CR5","first-page":"184","volume-title":"37th FOCS","author":"Y. Bartal","year":"1996","unstructured":"Bartal,\u00a0Y.: Probabilistic approximations of metric spaces and its algorithmic applications. In: 37th FOCS, pp.\u00a0184\u2013193 (1996)"},{"key":"9337_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"281","DOI":"10.1007\/3-540-48686-0_28","volume-title":"Proc. 5th Internat. Computing and Combinatorics Conference","author":"A.E.F. Clementi","year":"1999","unstructured":"Clementi, A.E.F., Crescenzi,\u00a0P., Rossi,\u00a0G.: On the complexity of approximating colored-graph problems. In: Proc. 5th Internat. Computing and Combinatorics Conference. Lecture Notes in Computer Science, vol.\u00a01627, pp.\u00a0281\u2013290. Springer, Berlin (1999)"},{"key":"9337_CR7","first-page":"762","volume-title":"16th SODA","author":"H.T.-H. Chan","year":"2005","unstructured":"Chan, H.T.-H., Gupta,\u00a0A., Maggs, B.M., Zhou,\u00a0S.: On hierarchical routing in doubling metrics. In: 16th SODA, pp.\u00a0762\u2013771 (2005)"},{"issue":"1","key":"9337_CR8","doi-asserted-by":"crossref","first-page":"63","DOI":"10.1007\/PL00009449","volume":"22","author":"K.L. Clarkson","year":"1999","unstructured":"Clarkson, K.L.: Nearest neighbor queries in metric spaces. Discrete Comput. Geom. 22(1), 63\u201393 (1999)","journal-title":"Discrete Comput. Geom."},{"key":"9337_CR9","doi-asserted-by":"crossref","first-page":"22","DOI":"10.1016\/j.jalgor.2005.01.010","volume":"57","author":"M. Berg de","year":"2005","unstructured":"de Berg,\u00a0M., Gudmundsson,\u00a0J., Katz, M.J., Levcopoulos,\u00a0C., Overmars, M.H., van\u00a0der Stappen, A.F.: TSP with neighborhoods of varying size. J.\u00a0Algorithms 57, 22\u201336 (2005)","journal-title":"J.\u00a0Algorithms"},{"key":"9337_CR10","series-title":"Algorithms and Combinatorics","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-04295-9","volume-title":"Geometry of Cuts and Metrics","author":"M.M. Deza","year":"1997","unstructured":"Deza, M.M., Laurent,\u00a0M.: Geometry of Cuts and Metrics. Algorithms and Combinatorics, vol.\u00a015. Springer, Berlin (1997)"},{"issue":"1","key":"9337_CR11","doi-asserted-by":"crossref","first-page":"135","DOI":"10.1016\/S0196-6774(03)00047-6","volume":"48","author":"A. Dumitrescu","year":"2003","unstructured":"Dumitrescu,\u00a0A., Mitchell, J.S.B.: Approximation algorithms for TSP with neighborhoods in the plane. J.\u00a0Algorithms 48(1), 135\u2013159 (2003)","journal-title":"J.\u00a0Algorithms"},{"issue":"4","key":"9337_CR12","doi-asserted-by":"crossref","first-page":"1019","DOI":"10.1137\/050636589","volume":"21","author":"M. Dror","year":"2008","unstructured":"Dror,\u00a0M., Orlin, J.B.: Combinatorial optimization with explicit delineation of the ground set by a collection of subsets. SIAM J. Discrete Math. 21(4), 1019\u20131034 (2008)","journal-title":"SIAM J. Discrete Math."},{"key":"9337_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"1115","DOI":"10.1007\/11523468_90","volume-title":"ICALP","author":"K. Elbassioni","year":"2005","unstructured":"Elbassioni,\u00a0K., Fishkin, A.V., Mustafa,\u00a0N., Sitters,\u00a0R.: Approximation algorithms for Euclidean group TSP. In: ICALP. Lecture Notes in Computer Science, vol.\u00a03580, pp.\u00a01115\u20131126. Springer, Berlin (2005)"},{"issue":"2","key":"9337_CR14","doi-asserted-by":"crossref","first-page":"173","DOI":"10.1142\/S0218195909002897","volume":"19","author":"K. Elbassioni","year":"2009","unstructured":"Elbassioni,\u00a0K., Fishkin, A.V., Sitters,\u00a0R.: Approximation algorithms for the Euclidean traveling salesman problem with discrete and continuous neighborhoods. Int. J. Comput. Geom. Appl. 19(2), 173\u2013193 (2009)","journal-title":"Int. J. Comput. Geom. Appl."},{"issue":"3","key":"9337_CR15","doi-asserted-by":"crossref","first-page":"485","DOI":"10.1016\/j.jcss.2004.04.011","volume":"69","author":"J. Fakcharoenphol","year":"2004","unstructured":"Fakcharoenphol,\u00a0J., Rao,\u00a0S., Talwar,\u00a0K.: A tight bound on approximating arbitrary metrics by tree metrics. J.\u00a0Comput. Syst. Sci. 69(3), 485\u2013497 (2004)","journal-title":"J.\u00a0Comput. Syst. Sci."},{"key":"9337_CR16","first-page":"101","volume-title":"Proceedings of the 21st European Workshop on Computational Geometry EWCG","author":"C. Feremans","year":"2005","unstructured":"Feremans,\u00a0C., Grigoriev,\u00a0A.: Approximation schemes for the generalized geometric problems with geographic clustering. In: Proceedings of the 21st European Workshop on Computational Geometry EWCG, pp.\u00a0101\u2013102 (2005)"},{"issue":"1","key":"9337_CR17","doi-asserted-by":"crossref","first-page":"66","DOI":"10.1006\/jagm.2000.1096","volume":"37","author":"N. Garg","year":"2000","unstructured":"Garg,\u00a0N., Konjevod,\u00a0G., Ravi,\u00a0R.: A polylogarithmic approximation algorithm for the group Steiner tree problem. J.\u00a0Algorithms 37(1), 66\u201384 (2000). Preliminary version in 9th SODA, pp.\u00a0253\u2013259 (1998)","journal-title":"J.\u00a0Algorithms"},{"issue":"4","key":"9337_CR18","first-page":"469","volume":"6","author":"J. Gudmundsson","year":"1999","unstructured":"Gudmundsson,\u00a0J., Levcopoulos,\u00a0C.: A fast approximation algorithm for TSP with neighborhoods. Nord. J. Comput. 6(4), 469\u2013488 (1999)","journal-title":"Nord. J. Comput."},{"key":"9337_CR19","first-page":"534","volume-title":"44th FOCS","author":"A. Gupta","year":"2003","unstructured":"Gupta,\u00a0A., Krauthgamer,\u00a0R., Lee, J.R.: Bounded geometries, fractals, and low-distortion embeddings. In: 44th FOCS, pp.\u00a0534\u2013543 (2003)"},{"key":"9337_CR20","first-page":"585","volume-title":"Proceedings of the 36th ACM Symposium on Theory of Computing","author":"E. Halperin","year":"2003","unstructured":"Halperin,\u00a0E., Krauthgamer,\u00a0R.: Polylogarithmic inapproximability. In: Proceedings of the 36th ACM Symposium on Theory of Computing, pp.\u00a0585\u2013594. ACM Press, New York (2003)"},{"key":"9337_CR21","doi-asserted-by":"crossref","first-page":"150","DOI":"10.1145\/1064092.1064117","volume-title":"21st SOCG","author":"S. Har-Peled","year":"2005","unstructured":"Har-Peled,\u00a0S., Mendel,\u00a0M.: Fast constructions of nets in low dimensional metrics, and their applications. In: 21st SOCG, pp.\u00a0150\u2013158 (2005)"},{"key":"9337_CR22","first-page":"798","volume-title":"15th SODA","author":"R. Krauthgamer","year":"2004","unstructured":"Krauthgamer,\u00a0R., Lee, J.R.: Navigating nets: Simple algorithms for proximity search. In: 15th SODA, pp.\u00a0798\u2013807 (2004)"},{"issue":"2\u20133","key":"9337_CR23","doi-asserted-by":"crossref","first-page":"262","DOI":"10.1016\/j.tcs.2005.09.017","volume":"348","author":"R. Krauthgamer","year":"2005","unstructured":"Krauthgamer,\u00a0R., Lee, J.R.: The black-box complexity of nearest-neighbor search. Theor. Comput. Sci. 348(2\u20133), 262\u2013276 (2005)","journal-title":"Theor. Comput. Sci."},{"key":"9337_CR24","doi-asserted-by":"crossref","first-page":"360","DOI":"10.1145\/220279.220318","volume-title":"Proc. 11th Annual ACM Symposium on Computational Geometry","author":"C.S. Mata","year":"1995","unstructured":"Mata, C.S., Mitchell, J.S.B.: Approximation algorithms for geometric tour and network design problems (extended abstract). In: Proc. 11th Annual ACM Symposium on Computational Geometry, pp.\u00a0360\u2013369 (1995)"},{"key":"9337_CR25","series-title":"Graduate Texts in Mathematics","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4613-0039-7","volume-title":"Lectures on Discrete Geometry","author":"J. Matou\u0161ek","year":"2002","unstructured":"Matou\u0161ek,\u00a0J.: Lectures on Discrete Geometry. Graduate Texts in Mathematics, vol.\u00a0212. Springer, New York (2002)"},{"issue":"4","key":"9337_CR26","doi-asserted-by":"crossref","first-page":"1298","DOI":"10.1137\/S0097539796309764","volume":"28","author":"J.S.B. Mitchell","year":"1999","unstructured":"Mitchell, J.S.B.: Guillotine subdivisions approximate polygonal subdivisions: A\u00a0simple polynomial-time approximation scheme for geometric TSP, k-MST, and related problems. SIAM J. Comput. 28(4), 1298\u20131309 (1999)","journal-title":"SIAM J. Comput."},{"key":"9337_CR27","first-page":"11","volume-title":"SODA","author":"J.S.B. Mitchell","year":"2007","unstructured":"Mitchell, J.S.B.: A PTAS for TSP with neighborhoods among fat regions in the plane. In: SODA, pp.\u00a011\u201318 (2007)"},{"key":"9337_CR28","first-page":"183","volume-title":"Symposium on Computational Geometry","author":"J.S.B. Mitchell","year":"2010","unstructured":"Mitchell, J.S.B.: A constant-factor approximation algorithm for TSP with pairwise-disjoint connected neighborhoods in the plane. In: Symposium on Computational Geometry, pp.\u00a0183\u2013191 (2010)"},{"key":"9337_CR29","first-page":"540","volume-title":"STOC \u201998","author":"S.B. Rao","year":"1999","unstructured":"Rao, S.B., Smith, W.D.: Approximating geometrical graphs via \u201cspanners\u201d and \u201cbanyans\u201d. In: STOC \u201998, Dallas, TX, pp.\u00a0540\u2013550. ACM, New York (1999)"},{"issue":"4","key":"9337_CR30","doi-asserted-by":"crossref","first-page":"281","DOI":"10.1007\/s00037-005-0200-3","volume":"14","author":"S. Safra","year":"2006","unstructured":"Safra, S., Schwartz, O.: On the complexity of approximating TSP with neighborhoods and related problems. Comput. Complex. 14(4), 281\u2013307 (2006)","journal-title":"Comput. Complex."},{"key":"9337_CR31","first-page":"281","volume-title":"36th STOC","author":"K. Talwar","year":"2004","unstructured":"Talwar,\u00a0K.: Bypassing the embedding: Algorithms for low-dimensional metrics. In: 36th STOC, pp.\u00a0281\u2013290 (2004)"},{"key":"9337_CR32","doi-asserted-by":"crossref","unstructured":"van\u00a0der Stappen, A.F.: Motion planning amidst fat obstacles. Ph.D. Dissertation, Department of Computer Science, Utrecht University, Utrecht, Netherlands (1994)","DOI":"10.1145\/177424.177453"}],"container-title":["Discrete & Computational Geometry"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/www.springerlink.com\/index\/pdf\/10.1007\/s00454-011-9337-9","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,6,5]],"date-time":"2023-06-05T20:12:40Z","timestamp":1685995960000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00454-011-9337-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,3,18]]},"references-count":32,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2011,12]]}},"alternative-id":["9337"],"URL":"https:\/\/doi.org\/10.1007\/s00454-011-9337-9","relation":{},"ISSN":["0179-5376","1432-0444"],"issn-type":[{"value":"0179-5376","type":"print"},{"value":"1432-0444","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,3,18]]}}}